Given a string S, your task is to find the number of patterns of form 1[0]1 where [0] represents any number of zeroes (minimum requirement is one 0) there should not be any other character except 0 in the [0] sequence.
Example 1:
Input:
S = "100001abc101"
Output: 2
Explanation:
The two patterns are "100001" and "101".
Example 2:
Input:
S = "1001ab010abc01001"
Output: 2
Explanation:
The two patterns are "1001"(at start)
and "1001"(at end).
User Task:
Your task is to complete the function patternCount() which takes a single argument(string S) and returns the count of patterns. You need not take any input or print anything.
Expected Time Complexity: O(|S|).
Expected Auxiliary Space: O(1).
Constraints:
1<=Length of String<=10^5

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Data structures

Starter code: #User function Template for python3

class Solution:
    def patternCount(self, S): 
        # code here 

Solutions:
class Solution:

	def patternCount(self, l):
		lenth = len(l)
		count = 0
		i = 0
		while i < lenth - 1:
			if l[i] == '1' and i < lenth - 1:
				j = i + 1
				while l[j] == '0' and j < lenth - 1:
					j += 1
					if l[j] == '1':
						count += 1
				if l[j] == '1':
					i = j
				else:
					i = j + 1
			else:
				i += 1
		return count


class Solution:

	def patternCount(self, S):
		while S.find('00') != -1:
			S = S.replace('00', '0')
		count = 0
		i = 0
		while i < len(S) - 2:
			i = S.find('1', i)
			if i == -1 or i + 2 >= len(S):
				break
			if S[i + 1] == '0' and S[i + 2] == '1':
				count += 1
				i += 1
			else:
				i += 1
		return count


class Solution:

	def patternCount(self, s):
		t = ''
		for i in s:
			if i != '0':
				t += i
			elif len(t):
				if t[-1] != '0':
					t += i
		c = 0
		for i in range(len(t) - 2):
			if t[i:i + 3] == '101':
				c += 1
		return c


class Solution:

	def patternCount(self, S):
		i = 0
		ans = 0
		while i < len(S):
			if S[i] == '1':
				flag = False
				i += 1
				while i < len(S) and S[i] == '0':
					flag = True
					i += 1
				if i < len(S) and S[i] == '1' and flag:
					ans += 1
			else:
				i += 1
		return ans


class Solution:

	def patternCount(self, S):
		n = len(S)

		def helper(i):
			while i < n and S[i] == '0':
				i += 1
			return i < n and S[i] == '1'
		count = 0
		for (i, item) in enumerate(S):
			if S[i:i + 2] == '10':
				count += helper(i + 1)
		return count


class Solution:

	def patternCount(self, S):
		length = len(S)
		oneseen = False
		count = 0
		for i in range(length):
			if S[i] == '1' and oneseen:
				if S[i - 1] == '0':
					count += 1
			if S[i] == '1' and oneseen == 0:
				oneseen = True
			if S[i] != '0' and S[i] != '1':
				oneseen = False
		return count


import re

class Solution:

	def patternCount(self, S):
		return len(re.findall('(?=(10+1))', S))


class Solution:

	def patternCount(self, S):
		(i, j) = (0, 0)
		l = 0
		l1 = ['0', '1']
		end = len(S)
		while i < end - 2:
			if S[i] == '1':
				j = i + 1
				while j < end:
					if S[j] == '1':
						if S[j - 1] == '0':
							l += 1
							i = j
							if i < end - 1:
								while not S[i] == '1':
									i += 1
									if i == end - 2:
										return l
							j = i + 1
							continue
						else:
							i = j
							j += 1
							continue
					elif S[j] == '0':
						while S[j] == '0':
							j += 1
							if j == end:
								return l
						continue
					else:
						i = j + 1
						while not S[i] == '1':
							i += 1
							if i == end - 2:
								return l
						j = i + 1
			i += 1
		return l


class Solution:

	def patternCount(self, S):
		count = 0
		for i in range(len(S) - 1):
			if i < len(S) and S[i] == '1' and (S[i + 1] == '0'):
				i += 1
				while i < len(S) and S[i] == '0':
					i += 1
				if i < len(S) and S[i] == '1':
					count += 1
					i -= 1
		return count


class Solution:

	def patternCount(self, S):
		last = S[0]
		c = 0
		i = 1
		while i < len(S):
			if S[i] == '0' and last == '1':
				while S[i] == '0' and i < len(S) - 1:
					i += 1
					if S[i] == '1':
						c += 1
			last = S[i]
			i += 1
		return c


from collections import deque

class Solution:

	def patternCount(self, S):
		pattern_count = 0
		d = deque()
		for i in S:
			if len(d) == 0:
				if i == '1':
					d.append(i)
			else:
				if i != '0' or i != '1':
					if d[-1] == '1' and i == '1':
						d.clear()
						d.append(i)
						continue
					if d[-1] == '1' and i == '0':
						d.append(i)
						continue
					if d[-1] == '0' and i == '0':
						d.append(i)
						continue
					if d[-1] == '0' and i == '1':
						pattern_count += 1
						d.clear()
						d.append(i)
						continue
				d.clear()
		return pattern_count


import re

class Solution:

	def patternCount(self, S):
		pattern = '(?=(1(0+)1))'
		match = re.findall(pattern, S)
		return len(match)


class Solution:

	def patternCount(self, S):
		flag = False
		count = 0
		zero = False
		for i in S:
			if i == '1' and flag == False:
				flag = True
			elif i == '0' and flag == True:
				zero = True
				continue
			elif i != '0' and flag == True and (i != '1'):
				flag = False
				zero = False
			elif i == '1' and flag == True and zero:
				count += 1
				zero = False
		return count


import re

class Solution:

	def patternCount(self, S):
		pattern = re.compile('(?=(10+1))')
		match = pattern.findall(S)
		return len(match)


class Solution:

	def patternCount(self, S):
		n = len(S)
		count = 0
		oneSeen = False
		for i in range(n):
			if S[i] == '1' and oneSeen:
				if S[i - 1] == '0':
					count += 1
			elif S[i] == '1':
				oneSeen = True
			elif S[i] != '0':
				oneSeen = False
		return count


class Solution:

	def patternCount(self, S):
		flag = 0
		pat = 0
		(i, j) = (0, 1)
		while j < len(S) and i < j:
			if S[i] == '1':
				if S[j] == '0':
					flag = 1
					j += 1
				elif S[j] == '1':
					if flag == 0:
						i = j
						j += 1
					if flag == 1:
						pat += 1
						i = j
						j += 1
						flag = 0
				else:
					i = j
					j += 1
					flag = 0
			else:
				i = j
				j += 1
		return pat


class Solution:

	def patternCount(self, S):
		cont = 0
		i = 0
		if '0' not in S:
			return 0
		while i < len(S) - 2:
			if S[i] == '1':
				while i < len(S) - 1 and S[i + 1] == '0':
					i += 1
				if S[i + 1] == '1' and S[i] == '0':
					cont += 1
					i += 1
				else:
					i += 1
			else:
				i += 1
		return cont


class Solution:

	def patternCount(self, S):
		res = i = 0
		while i < len(S):
			while i < len(S) and S[i] != '1':
				i += 1
			i += 1
			while i < len(S):
				if S[i] == '0':
					i += 1
				elif S[i] == '1' and S[i - 1] == '0':
					res += 1
					break
				else:
					break
		return res


class Solution:

	def patternCount(self, s):
		e = s[0]
		for i in s[1:]:
			if e[-1] != i:
				e += i
		c = 0
		for i in range(len(e) - 2):
			if e[i] == '1' and e[i + 1] == '0' and (e[i + 2] == '1'):
				c += 1
		return c


class Solution:

	def patternCount(self, S):
		i = 1
		n = len(S)
		count = 0
		while i < n:
			if S[i - 1] == '1' and S[i] == '0':
				while i < n and S[i] == '0':
					i += 1
				if i < n and S[i] == '1':
					count += 1
					i -= 1
			i += 1
		return count


class Solution:

	def patternCount(self, S):
		cnt = 0
		c = ''
		for i in S:
			if not c:
				if i == '1':
					c += i
			elif i != '0' and i != '1':
				c = ''
			elif i == '0':
				c += i
			elif c[-1] == '0':
				cnt += 1
				c = '1'
		return cnt


class Solution:

	def patternCount(self, S):
		c = 0
		z = 0
		res = []
		for (j, i) in enumerate(S):
			if i.isdigit() == False:
				res = []
			if i == '1':
				if j > 0 and S[j - 1] != '1':
					res.append(1)
				if j == 0:
					res.append(1)
				c = 0
			if i == '0':
				if c == 0:
					res.append(0)
				c += 1
			if res == [1, 0, 1] or res == [0, 1, 0, 1]:
				z += 1
				res = [1]
			elif i.isdigit() and i != '1' and (i != '0'):
				res = []
		return z


class Solution:

	def patternCount(self, S):
		c = 0
		flag = 0
		xflag = 0
		for i in S:
			if i == '1':
				if flag == 1 and xflag == 1:
					c = c + 1
					xflag = 0
				flag = 1
			elif i == '0':
				if flag == 1:
					xflag = 1
			else:
				flag = 0
				xflag = 0
		return c


class Solution:

	def patternCount(self, S):
		ans = '#'
		n = len(S)
		count = 0
		for i in range(n):
			if S[i] == '1':
				if ans[-1] != '0':
					ans += '1'
				else:
					count += 1
					ans = '1'
			elif S[i] == '0':
				if ans[-1] == '1':
					ans += '0'
			else:
				ans = '#'
		return count


class Solution:

	def patternCount(self, S):
		res = 0
		s = 0
		n = len(S)
		i = 0
		z = 0
		while i < n:
			if S[i] == '1':
				if s and z:
					res += 1
					z = 0
				else:
					s = 1
			elif s:
				if S[i] != '0':
					s = 0
					z = 0
				else:
					z = 1
			i += 1
		return res


class Solution:

	def patternCount(self, S):
		n = len(S)
		prev = -1
		res = 0
		for i in range(n):
			if S[i] == '1':
				if prev != -1:
					if i - prev > 1:
						res += 1
				prev = i
			elif S[i] != '0':
				prev = -1
		return res


class Solution:

	def patternCount(self, S):
		f1 = 0
		s1 = 0
		z = 0
		c = 0
		for i in S:
			if f1 == 0 and i == '1':
				f1 = 1
			elif f1 == 1 and i == '0':
				z = 1
			elif f1 == 1 and z == 1 and (i == '1'):
				c += 1
				f1 = 1
				z = 0
				s1 = 0
			elif f1 == 1 and i == '1':
				pass
			else:
				f1 = 0
				z = 0
				s1 = 0
		return c
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		S = input()
		ob = Solution()
		print(ob.patternCount(S))


class Solution:

	def patternCount(self, S):
		count = 0
		seen = False
		for i in range(len(S)):
			if S[i] == '1' and seen == True:
				if S[i - 1] == '0':
					count += 1
			elif S[i] == '1' and seen == False:
				seen = True
			elif S[i] != '0' and S[i] != '1':
				seen = False
		return count
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		S = input()
		ob = Solution()
		print(ob.patternCount(S))


class Solution:

	def patternCount(self, s):
		count = 0
		pattern_started = False
		pattern_progress = False
		for i in range(len(s)):
			if pattern_started == False and pattern_progress == False and (s[i] == '1'):
				pattern_started = True
			elif pattern_started == True and pattern_progress == False and (s[i] == '0'):
				pattern_progress = True
			elif pattern_started == True and pattern_progress == False and (s[i] == '1'):
				pattern_started = True
			elif pattern_started == True and pattern_progress == False:
				pattern_started = False
			elif pattern_started == True and pattern_progress == True and (s[i] not in ('0', '1')):
				pattern_started = False
				pattern_progress = False
			elif pattern_started == True and pattern_progress == True and (s[i] == '1'):
				count = count + 1
				pattern_started = True
				pattern_progress = False
		return count


class Solution:

	def patternCount(self, S):
		s = S
		p1 = -1
		z = 0
		c = 0
		k = -1
		j = 0
		for i in range(len(s)):
			if s[i] == '1':
				if p1 == -1:
					p1 = i
				else:
					k = i
					j = k - p1 - 1
					if z == j and z != 0:
						c = c + 1
						p1 = k
						z = 0
					else:
						p1 = k
						z = 0
			elif s[i] == '0':
				if p1 != -1:
					z = z + 1
		return c


class Solution:

	def patternCount(self, S):
		res = list(S)
		count = 0
		c = 10000000
		n = len(res)
		for i in range(n - 1):
			if res[i] == '1' and res[i + 1] == '0':
				c = i + 1
			if i == c and res[i + 1] == '1':
				count += 1
			if i == c and res[i + 1] == '0':
				c = i + 1
		return count


class Solution:

	def patternCount(self, S):
		n = len(S)
		i = 0
		count = 0
		while i < n:
			if S[i] != '1':
				i += 1
				continue
			j = i + 1
			flag = 0
			while j < n and S[j] != '1':
				if S[j] != '0':
					flag = 1
				j += 1
			if flag != 1 and j - i > 1:
				if j == n and S[j - 1] == '1':
					count += 1
				elif j != n:
					count += 1
			i = j
		return count


class Solution:

	def patternCount(self, s):
		last = s[0]
		i = 0
		res = 0
		while i < len(s):
			if s[i] == '0' and last == '1':
				while i < len(s) - 1 and s[i] == '0':
					i += 1
				if s[i] == '1':
					res += 1
			last = s[i]
			i += 1
		return res


class Solution:

	def patternCount(self, S):
		start = False
		zero = False
		ans = 0
		i = 0
		j = len(S)
		while i < j:
			if S[i] != '0' and S[i] != '1':
				start = False
				zero = False
			elif S[i] == '1' and (not start):
				start = True
			elif S[i] == '1' and start and zero:
				ans += 1
				zero = False
			elif S[i] == '0' and start:
				zero = True
			i += 1
		return ans


class Solution:

	def patternCount(self, S):
		c = 0
		s = ''
		for i in range(0, len(S)):
			if len(s) == 0 and S[i] == '1':
				s += S[i]
			elif len(s) != 0:
				if S[i] == '0':
					s += S[i]
				elif S[i] == '1':
					s += S[i]
					if len(s) != 2:
						c += 1
					s = ''
					s += S[i]
				else:
					s = ''
		return c


class Solution:

	def patternCount(self, S):
		n = len(S)
		i = 0
		el = 0
		count = 0
		while i < n:
			if S[i] == '1':
				if el == 0:
					el = 1
				elif el == 2:
					count += 1
					el = 1
			elif S[i] == '0':
				if el == 1:
					el = 2
			else:
				el = 0
			i += 1
		return count


class Solution:

	def patternCount(self, s):
		cout = 0
		bool = False
		c = 0
		i = 0
		while i < len(s):
			if s[i] == '1' and (not bool):
				bool = True
				i += 1
			elif bool and s[i] == '0':
				c += 1
				i += 1
			elif bool and c > 0 and (s[i] == '1'):
				cout += 1
				c = 0
				bool = False
			elif bool and c == 0 and (s[i] == '1'):
				bool = False
			else:
				i += 1
				c = 0
				bool = False
		return cout


class Solution:

	def patternCount(self, s):
		import re
		regext = re.compile('(?=(10+1))')
		str = regext.finditer(s)
		c = 0
		for i in str:
			c = c + 1
		return c


class Solution:

	def patternCount(self, S):
		count_101 = 0
		for outer in range(len(S) - 2):
			if S[outer] == '1':
				zero_count = 0
				for inner in range(outer + 1, len(S)):
					if S[inner] == '0':
						zero_count += 1
					if S[inner] == '1' and zero_count:
						count_101 += 1
						break
					if S[inner] != '0':
						break
		return count_101


class Solution:

	def patternCount(self, S):
		count = 0
		i = 0
		j = i + 1
		n = len(S)
		while i < n and j < n:
			if S[i] == '1' and S[j] == '0':
				j = j + 1
				continue
			elif S[j] == '1' and i != j - 1 and (S[i] == '1'):
				count = count + 1
				if j >= n - 2:
					break
				i = j
				j = i + 1
			elif j >= n - 2:
				break
			else:
				i = j
				j = i + 1
		return count


class Solution:

	def patternCount(self, S):
		count = 0
		last = S[0]
		i = 1
		while i < len(S):
			if S[i] == '0' and last == '1':
				while i < len(S) and S[i] == '0':
					i += 1
				if i >= len(S):
					break
				if S[i] == '1':
					count += 1
			last = S[i]
			i += 1
		return count