Given a binary string (consists of only 0 and 1). If there is “100” as a sub-string in the string, then we can delete this sub-string. The task is to find the length of longest sub-string which can be make removed?
Example 1:
Input  : 
str = "1011100000100"
Output :
6
Explanation :
Sub-strings present in str that can be make
removed 101{110000}0{100}. First
sub-string 110000-->100-->null, length is = 6.
Second sub-string 100-->null, length is = 3
 
Example 2:
Input  :
str = "111011"
Output :
0
Explanation :
There is no sub-string which can be make null.
 
Your Task:  
You don't need to read input or print anything. Your task is to complete the function longestNull() which takes the string S[] as inputs and returns the length of the longest string that can be removed.
 
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ string length ≤ 10^{4}
S[i] = {0, 1}

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Data structures

Starter code: #User function Template for python3

class Solution:
    def longestNull(self,S):
        # Your code goes here 

Solutions:
class Solution:

	def longestNull(self, S):
		arr = []
		arr.append(['@', -1])
		maxlen = 0
		for i in range(len(S)):
			arr.append([S[i], i])
			while len(arr) >= 3 and arr[len(arr) - 3][0] == '1' and (arr[len(arr) - 2][0] == '0') and (arr[len(arr) - 1][0] == '0'):
				arr.pop()
				arr.pop()
				arr.pop()
			temp = arr[-1]
			maxlen = max(maxlen, i - temp[1])
		return maxlen


class Solution:

	def longestNull(self, S):
		arr = []
		arr.append(['@', -1])
		max_len = 0
		n = len(S)
		for i in range(n):
			arr.append([S[i], i])
			while len(arr) >= 3 and arr[len(arr) - 3][0] == '1' and (arr[len(arr) - 2][0] == '0') and (arr[len(arr) - 1][0] == '0'):
				arr.pop()
				arr.pop()
				arr.pop()
			last = arr[-1][1]
			max_len = max(max_len, i - last)
		return max_len


class Solution:

	def longestNull(self, S):
		l = []
		l.append(['2', -1])
		mx = 0
		for i in range(len(S)):
			l.append([S[i], i])
			while len(l) >= 3 and l[-3][0] == '1' and (l[-2][0] == '0') and (l[-1][0] == '0'):
				l.pop()
				l.pop()
				l.pop()
				mx = max(mx, i - l[-1][1])
		return mx

def main():
	T = int(input())
	while T > 0:
		s = input()
		ob = Solution()
		print(ob.longestNull(s))
		T -= 1
if __name__ == '__main__':
	main()