Given a binary string S of 0 and 1, check if the given string is valid or not. The given string is valid when there is no zero is present in between 1s.
Example 1:
Input:
S = "100"
Output: VALID
Explanation: 100. The string have just a
single 1, hence it is valid.
Example 2:
Input: 
S = "1110001"
Output: INVALID
Explanation: 1110001. There are 3 zeros
between the 3rd and the 4th ones. Hence,
it's an invalid string.
Your Task:
You don't need to read input or print anything, Your task is to complete the function checkBinary() which takes a binary string as input are returns true if the string is valid. Else, it returns false.
Expected Time Complexity: O(|S|).
Expected Auxiliary Space: O(1).
Constraints:
1<=length(S)<=10^{5 }

Difficulty: EASY
Tags: String algorithms

Bit manipulation

Data structures
Skill types: Bit manipulation

Data structures
Expected Time Complexity: O(|S|).
Expected Auxiliary Space: O(1).

Starter code:
#User function Template for python3



class Solution:

    def checkBinary (self, s):

        # Your code here

Solutions:
class Solution:

	def checkBinary(self, s):
		(one, zero) = (0, 0)
		for i in s:
			if i == '1':
				if zero == 1 and one == 1:
					return False
				one = 1
			if i == '0' and one == 1:
				zero = 1
		return True


class Solution:

	def checkBinary(self, s):
		st = []
		for i in range(len(s)):
			if s[i] == '1' and (not st):
				st.append('1')
				continue
			if s[i] == '0' and st and (st[-1] != '0'):
				st.append('0')
			if s[i] == '1' and st and (st[-1] == '0'):
				return False
		return True


class Solution:

	def checkBinary(self, s):
		while s and s[0] == '0':
			s = s[1:]
		while s and s[0] == '1':
			s = s[1:]
		for i in s:
			if i == '1':
				return 0
		return 1


class Solution:

	def checkBinary(self, s):
		ans = True
		flag_one = 0
		flag_zero = 0
		for i in range(len(s)):
			if s[i] == '1' and flag_zero == 0:
				flag_one = 1
			elif s[i] == '0' and flag_one == 1:
				flag_zero = 1
			elif s[i] == '1' and flag_zero == 1:
				ans = False
				return ans
		return ans


class Solution:

	def checkBinary(self, s):
		mode = 1
		for i in s:
			if mode == 1 and i == '1':
				mode = 2
			elif mode == 2 and i == '0':
				mode = 3
			elif mode == 3 and i == '1':
				return 0
		return 1


class Solution:

	def checkBinary(self, s):
		n = len(s)
		i = 0
		while i < n and s[i] == '0':
			i += 1
		while i < n and s[i] == '1':
			i += 1
		while i < n:
			if s[i] == '1':
				return False
			i += 1
		return True


class Solution:

	def checkBinary(self, s):
		temp = ''
		temp += s[0]
		for i in range(1, len(s)):
			if temp[-1] != s[i]:
				temp += s[i]
		if '101' in temp:
			return 0
		else:
			return 1


class Solution:

	def checkBinary(self, s):
		while s and s[0] == '0':
			s = s[1:]
		while s and s[0] == '1':
			s = s[1:]
		while s and s[0] == '0':
			s = s[1:]
		return not s


class Solution:

	def checkBinary(self, s):
		flag1 = False
		flag2 = False
		for i in range(len(s)):
			if s[i] == '1' and flag2 == True and (flag1 == True):
				if s[i - 1] == '0':
					return False
			if s[i] == '1' and flag2 == False and (flag1 == True):
				continue
			if s[i] == '1' and flag1 == False:
				flag1 = True
			if s[i] == '0' and flag2 == False:
				flag2 = True
				continue
			if s[i] == '0' and flag2 == True:
				continue
		return True


class Solution:

	def checkBinary(self, s):
		if s.__contains__('1'):
			i = s.index('1')
			j = s.rindex('1') + 1
			return not s[i:j].__contains__('0')
		return True


class Solution:

	def checkBinary(self, s):
		current = None
		for i in s:
			if i == '1':
				if current == None:
					current = 1
				elif current == 0:
					return False
			elif current == 1:
				current = 0
		return True


class Solution:

	def checkBinary(self, s):
		return not '0' in s.strip('0')


class Solution:

	def checkBinary(self, S):
		z = 0
		j = 0
		for i in range(len(S)):
			if S[i] == '0':
				continue
			else:
				j = i
				break
		for i in range(j + 1, len(S), 1):
			if S[i] == '1':
				if z == 1:
					return 0
			if S[i] == '0':
				z = 1
		return 1


class Solution:

	def checkBinary(self, s):
		(one_stack, zero_stack) = (0, 0)
		for i in s:
			if i == '1':
				if zero_stack and one_stack:
					return False
				one_stack = 1
			if i == '0' and one_stack:
				zero_stack = 1
		return True


class Solution:

	def checkBinary(self, s):
		if s.count('1') == 1:
			return True
		for i in range(1, len(s) - 1):
			if s[i] == '0':
				t = i
				if '1' in s[i + 1:] and s[i - 1] == '1':
					return False
		return True


class Solution:

	def checkBinary(self, s):
		count = 0
		for i in range(1, len(s)):
			if s[i - 1] == '1' and s[i] == '0':
				count = 1
			elif count == 1 and s[i - 1] == '0' and (s[i] == '1'):
				count = 2
				break
		if count == 2:
			return 0
		return 1


class Solution:

	def checkBinary(self, s):
		arr = []
		for i in range(len(s)):
			if not s[i] in arr and arr == [] and (s[i] == '1'):
				arr.append(s[i])
			elif s[i] == '0' and (not s[i] in arr) and (not arr == []):
				arr.append(s[i])
			elif arr.count(s[i]) < 2 and s[i] == '1' and (arr[-1] == '0'):
				arr.append(s[i])
		arr = ''.join(arr)
		return True if not arr == '101' else False


class Solution:

	def checkBinary(self, s):
		ones = 0
		zeros = 0
		n = len(s)
		if s[0] == '1':
			ones = 1
		else:
			zeros = 1
		i = 1
		while i < n:
			while i < n and s[i] == s[i - 1]:
				i += 1
			if i >= n:
				break
			if s[i] == '1':
				if ones == 1 and zeros == 1:
					return False
				ones = 1
			else:
				zeros = 1
			i += 1
		return True


class Solution:

	def checkBinary(self, s):
		result = 'VALID'
		for i in range(0, len(s)):
			if s[i] == '1':
				for j in range(i + 1, len(s)):
					if s[j] == '1' and '0' in s[i:j + 1]:
						return False
		return True


class Solution:

	def checkBinary(self, s):
		lastIndexOf1 = 0
		for i in range(len(s) - 1, -1, -1):
			if s[i] == '1':
				lastIndexOf1 = i
				break
		startIndexOf1 = 0
		for i in range(len(s)):
			if s[i] == '1':
				startIndexOf1 = i
				break
		for i in range(len(s)):
			if s[i] == '0':
				if startIndexOf1 < i and lastIndexOf1 > i:
					return False
		return True


class Solution:

	def checkBinary(self, s):
		if s.count('1') >= 2:
			for i in range(len(s) - 1):
				if s[i] == '1':
					for j in range(i + 1, len(s)):
						if s[j] == '1':
							temp = s[i:j + 1]
							if '0' in temp:
								return False
		else:
			return True
		return True


class Solution:

	def checkBinary(self, s):
		p = ''
		a = s.find('1')
		p = s[a:]
		if '0' not in p:
			return True
		else:
			b = p.find('0')
			for i in range(b + 1, len(p)):
				if p[i] == '1':
					return False
		return True


class Solution:

	def checkBinary(self, s):
		ones = s.count('1')
		if ones == 0:
			return True
		i = s.index('1')
		ic = 0
		l = 0
		while l < len(s) and s[i] == '1':
			i += 1
			ic += 1
			l += 1
			if i == len(s):
				break
		return False if ones - ic > 0 else True


class Solution:

	def checkBinary(self, s):
		mode = 1
		for i in s:
			if mode == 1 and i == '1':
				mode = 2
			elif mode == 2 and i == '0':
				mode = 3
			elif mode == 3 and i == '1':
				return 0
		return 1
t = int(input())
for tc in range(t):
	s = input()
	ob = Solution()
	if ob.checkBinary(s) == True:
		print('VALID')
	else:
		print('INVALID')


class Solution:

	def checkBinary(self, s):
		count = 0
		for i in range(1, len(s)):
			if s[i - 1] == '1' and s[i] == '0':
				count = 1
			elif count == 1 and s[i - 1] == '0' and (s[i] == '1'):
				count = 2
				break
		if count == 2:
			return 0
		return 1
t = int(input())
for tc in range(t):
	s = input()
	ob = Solution()
	if ob.checkBinary(s) == True:
		print('VALID')
	else:
		print('INVALID')


class Solution:

	def checkBinary(self, s):
		if s.count('1') == 0:
			return True
		x = s.index('1')
		x1 = s[::-1].index('1')
		x1 = len(s) - x1
		c = 0
		for i in range(x, x1):
			if s[i] == '0':
				c += 1
		if c == 0:
			return True
		else:
			return False
t = int(input())
for tc in range(t):
	s = input()
	ob = Solution()
	if ob.checkBinary(s) == True:
		print('VALID')
	else:
		print('INVALID')


class Solution:

	def checkBinary(self, s):
		for i in range(len(s)):
			if s[i] == '1':
				break
		for j in range(len(s) - 1, -1, -1):
			if s[j] == '1':
				break
		for p in range(i + 1, j, 1):
			if s[p] == '0':
				return False
		return True
t = int(input())
for tc in range(t):
	s = input()
	ob = Solution()
	if ob.checkBinary(s) == True:
		print('VALID')
	else:
		print('INVALID')


class Solution:

	def checkBinary(self, s):
		a = False
		b = False
		for i in s:
			if i == '1' and (not a):
				a = True
			if a and (not b) and (i == '0'):
				b = True
			if b and i == '1':
				return False
		return True
t = int(input())
for tc in range(t):
	s = input()
	ob = Solution()
	if ob.checkBinary(s) == True:
		print('VALID')
	else:
		print('INVALID')


class Solution:

	def checkBinary(self, s):
		flag = False
		for i in range(1, len(s)):
			if s[i] == '0':
				if s[i - 1] == '1':
					flag = True
			elif flag == True:
				return False
		return True
t = int(input())
for tc in range(t):
	s = input()
	ob = Solution()
	if ob.checkBinary(s) == True:
		print('VALID')
	else:
		print('INVALID')


class Solution:

	def checkBinary(self, s):
		b = s.strip('0')
		for i in b:
			if i == '0':
				return False
		return True
t = int(input())
for tc in range(t):
	s = input()
	ob = Solution()
	if ob.checkBinary(s) == True:
		print('VALID')
	else:
		print('INVALID')


class Solution:

	def checkBinary(self, s):
		lst = list(s)
		if '1' not in lst:
			return True
		indx1 = lst.index('1')
		lst.reverse()
		indx2 = len(lst) - 1 - lst.index('1')
		lst.reverse()
		if '0' in lst[indx1:indx2 + 1]:
			return False
		else:
			return True
t = int(input())
for tc in range(t):
	s = input()
	ob = Solution()
	if ob.checkBinary(s) == True:
		print('VALID')
	else:
		print('INVALID')


class Solution:

	def checkBinary(self, s):
		pv = s[0]
		flag = 0
		for i in s:
			if i == '0' and pv == '1':
				flag = 1
			elif i == '1' and pv == '0' and (flag == 1):
				flag = 2
				return False
			pv = i
		return True


class Solution:

	def checkBinary(self, s):
		g = 0
		f = 0
		for i in s:
			if i == '1' and g == 0:
				f = 1
			elif f == 1 and i == '0':
				g = 1
			elif i == '1' and g == 1:
				return False
		return True


class Solution:

	def checkBinary(self, s):
		if s.count('1') <= 1:
			return True
		i1 = s.find('1')
		i2 = s.rfind('1')
		sub = s[i1:i2 + 1]
		if '0' in sub:
			return False
		else:
			return True


class Solution:

	def checkBinary(self, s):
		n = len(s)
		first = len(s) + 1
		for i in range(n):
			if s[i] == '1':
				first = i
				break
			last = 0
		for i in range(n - 1, -1, -1):
			if s[i] == '1':
				last = i
				break
		for i in range(first, last + 1):
			if s[i] == '0':
				return False
		return True


class Solution:

	def checkBinary(self, s):
		if '1' in s:
			p = s.index('1')
			l = s[::-1]
			k = l.index('1')
			k = len(l) - k - 1
			if '0' in s[p:k + 1]:
				return 0
		return 1


class Solution:

	def checkBinary(self, s):
		one = []
		zero = []
		for i in range(len(s)):
			if s[i] == '1':
				one.append(i)
			else:
				zero.append(i)
		if len(one) <= 1:
			return True
		else:
			for i in zero:
				if i > one[0] and i < one[-1]:
					return False
			return True


class Solution:

	def checkBinary(self, s):
		flagstart = 0
		for i in range(len(s)):
			if s[i] == '1' and flagstart == 0 and (i + 1 < len(s)) and (s[i + 1] == '0'):
				flagstart += 1
			elif s[i] == '1' and flagstart > 0:
				return False
		return True


class Solution:

	def checkBinary(self, s):
		start = False
		middle_zero = False
		for i in range(len(s)):
			x = i + 1
			if s[-x] == '0' and start:
				middle_zero = True
			if s[-x] == '1':
				start = True
			if s[-x] == '1' and middle_zero:
				return False
		return True


class Solution:

	def checkBinary(self, s):
		if '1' in s:
			k = s.index('1')
			m = s[::-1].index('1')
			if '0' in s[k + 1:-m - 1]:
				return 0
			return 1
		else:
			return 1


class Solution:

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


import re

class Solution:

	def checkBinary(self, s):
		P = re.compile('10+1')
		R = P.search(s)
		return not R


import re

class Solution:

	def checkBinary(self, s):
		P = re.compile('10+1')
		R = P.search(s)
		return False if R != None else True


import re

class Solution:

	def checkBinary(self, s):
		pat = '(1+0+1)'
		lx = re.findall(pat, s)
		if len(lx) >= 1:
			return False
		return True


class Solution:

	def checkBinary(self, s):
		nums = []
		for i in range(len(s)):
			if s[i] == '1':
				nums.append(i + 1)
		if len(nums) > 1:
			if max(nums) - min(nums) + 1 != len(nums):
				return False
			else:
				return True
		else:
			return True


class Solution:

	def checkBinary(self, s):
		one = []
		zero = []
		for i in range(len(s)):
			if s[i] == '1':
				one.append(i)
			else:
				zero.append(i)
		if zero == [] or one == []:
			return 1
		else:
			for i in zero:
				if i > min(one) and i < max(one):
					return 0
			return 1


class Solution:

	def checkBinary(self, s):
		first_flag = False
		for i in range(len(s) - 1):
			if s[i:i + 2] == '10':
				first_flag = True
			elif s[i:i + 2] == '01' and first_flag:
				return False
		return True


class Solution:

	def checkBinary(self, s):
		start_1_idx = -1
		end_1_idx = -1
		for i in range(len(s)):
			if s[i] == '1':
				start_1_idx = i
				break
		for i in range(len(s) - 1, -1, -1):
			if s[i] == '1':
				end_1_idx = i
				break
		i = start_1_idx
		for i in range(start_1_idx, end_1_idx):
			if s[i] == '0':
				return False
		return True