Given a binary string S consisting of 0s and 1s. The task is to find the maximum difference of the number of 0s and the number of 1s (number of 0s – number of 1s) in the substrings of a string.
Note: In the case of all 1s, the answer will be -1. 
Example 1:
Input : S = "11000010001" 
Output : 6 
Explanatio: From index 2 to index 9, 
there are 7 0s and 1 1s, so number 
of 0s - number of 1s is 6. 
Example 2:
Input: S = "111111"
Output: -1
Explanation: S contains 1s only 
Your task:
You do not need to read any input or print anything. The task is to complete the function maxSubstring(), which takes a string as input and returns an integer. 
Expected Time Complexity: O(|S|)
Expected Auxiliary Space: O(|S|)
Constraints:
1 ≤ |S| ≤ 10^{5}
S contains 0s and 1s only

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Dynamic programming

Data structures

Starter code: #User function Template for python3
class Solution:
	def maxSubstring(self, S):
		# code here

Solutions:
import numpy as np

class Solution:

	def rec_sol(self, S, n):
		if n == 0:
			return 0
		if S[n - 1] == 1:
			return self.rec_sol(S, n - 1) - 1
		else:
			return self.rec_sol(S, n - 1) + 1

	def dp_sol(self, S):
		n = len(S)
		dp = np.array([0] * (n + 1))
		for j in range(n):
			if S[j] == '1':
				dp[j + 1] = max(dp[j] - 1, -1)
			else:
				dp[j + 1] = max(dp[j] + 1, 1)
		return np.max(dp)

	def maxSubstring(self, S):
		for el in S:
			if el == '0':
				return self.dp_sol(S)
		return -1


class Solution:

	def maxSubstring(self, S):
		if '0' not in s:
			return -1
		n = len(s)
		countone = countzero = mxdiff = 0
		for i in range(n):
			if s[i] == '0':
				countzero += 1
			else:
				countone += 1
			mxdiff = max(mxdiff, countzero - countone)
			if countone > countzero:
				countzero = countone = 0
		return mxdiff


class Solution:

	def maxSubstring(self, S):
		currSum = 0
		maxSum = 0
		for elem in S:
			if elem == '1':
				currSum -= 1
			else:
				currSum += 1
			if currSum < 0:
				currSum = 0
			maxSum = max(maxSum, currSum)
		return maxSum if maxSum else -1


class Solution:

	def maxSubstring(self, S):
		n = len(S)
		mx = 0
		val = 0
		f = False
		for i in range(n):
			if S[i] == '0':
				val += 1
			else:
				val -= 1
			mx = max(mx, val)
			if val <= 0:
				val = 0
		if mx == 0:
			return -1
		return mx


class Solution:

	def maxSubstring(self, S):
		s = 0
		cs = -1
		n = len(S)
		for e in S:
			if e == '0':
				s += 1
				if cs < s:
					cs = s
			elif s <= 0:
				s = 0
			else:
				s -= 1
		if S.count('1') == n:
			return -1
		else:
			return cs


class Solution:

	def maxSubstring(self, S):
		ans = -1
		sum1 = -1
		a = 0
		b = 0
		for i in range(len(S)):
			if S[i] == '1':
				b += 1
			else:
				a += 1
			sum1 = a - b
			if sum1 < 0:
				sum1 = -1
				a = 0
				b = 0
			ans = max(ans, sum1)
		return ans


class Solution:

	def maxSubstring(self, S):
		curr_sum = 0
		result = -1
		if S.count('1') == len(S):
			return -1
		for i in range(len(S)):
			if S[i] == '0':
				curr_sum += 1
			else:
				curr_sum -= 1
			if curr_sum < 0:
				curr_sum = 0
			result = max(result, curr_sum)
		return result


class Solution:

	def maxSubstring(self, S):
		curr_sum = 0
		max_sum = 0
		n = len(S)
		for i in range(n):
			curr_sum += 1 if S[i] == '0' else -1
			if curr_sum < 0:
				curr_sum = 0
			max_sum = max(max_sum, curr_sum)
		return max_sum if max_sum else -1


class Solution:

	def maxSubstring(self, S):
		if '0' not in S:
			return -1
		c1 = c0 = maxd = 0
		for i in range(len(S)):
			if S[i] == '0':
				c0 += 1
			else:
				c1 += 1
			maxd = max(maxd, c0 - c1)
			if c1 > c0:
				c1 = c0 = 0
		return maxd


class Solution:

	def maxSubstring(self, s):
		count = 0
		for i in s:
			if i == '1':
				count += 1
		if count == len(s):
			return -1
		maxval = 0
		currval = 0
		for i in s:
			if i == '0':
				currval += 1
			else:
				currval -= 1
				if currval < 0:
					currval = 0
			maxval = max(maxval, currval)
		return maxval


class Solution:

	def maxSubstring(self, S):
		maxdiff = -1
		differ_element = 0
		zero = 0
		one = 0
		for i in range(len(S)):
			if S[i] == '0':
				zero += 1
			else:
				one += 1
			differ_element = zero - one
			maxdiff = max(maxdiff, differ_element)
			if differ_element < 0:
				differ_element = 0
				zero = 0
				one = 0
		return maxdiff


class Solution:

	def maxSubstring(self, S):
		m = -10 ** 9
		c = 0
		for i in range(len(S)):
			if c < 0:
				c = 0
			if S[i] == '0':
				c += 1
			else:
				c -= 1
			m = max(m, c)
		return m


class Solution:

	def maxSubstring(self, S):
		n = len(S)
		dp = [-1] * n
		if S[0] == '0':
			dp[0] = 1
		for i in range(1, n):
			c = -1 if S[i] == '1' else 1
			dp[i] = max(c, dp[i - 1] + c)
		return max(dp)


class Solution:

	def maxSubstring(self, s):
		maxdif = cur = 0
		for i in s:
			if i == '0':
				cur += 1
			else:
				cur -= 1
			if cur < 0:
				cur = 0
			maxdif = max(maxdif, cur)
		if maxdif == 0:
			return -1
		return maxdif


class Solution:

	def count_zeros(self, s):
		count = 0
		for i in s:
			if i == '0':
				count += 1
		return count

	def maxSubstring(self, S):
		max_diff = -1
		count = 0
		min_diff = 0
		n = len(S)
		for i in range(n):
			if S[i] == '0':
				count += 1
			else:
				count -= 1
			if count - min_diff > max_diff:
				max_diff = count - min_diff
			if count < min_diff:
				min_diff = count
		return max_diff


class Solution:

	def maxSubstring(self, S):
		on = 0
		(maxx, cur) = (0, 0)
		for each in S:
			if each == '1':
				cur -= 1
				on += 1
			else:
				cur += 1
				on -= 1
			if cur < 0:
				cur = 0
			maxx = max(maxx, cur)
		if len(S) == on:
			return -1
		return maxx


class Solution:

	def maxSubstring(self, s):
		(a, b, md, m) = (0, 0, -1, 0)
		for i in range(len(s)):
			if s[i] == '0':
				a += 1
			else:
				b += 1
			m = a - b
			if m > md:
				md = m
			if m < 0:
				(m, a, b) = (0, 0, 0)
		return md


class Solution:

	def maxSubstring(self, S):
		(sum, res) = (0, -1)
		for x in S:
			if x == '1':
				sum -= 1
			else:
				sum += 1
			res = max(res, sum)
			if sum < 0:
				sum = 0
		return res


class Solution:

	def maxSubstring(self, S):
		max_diff = 0
		curr_diff = 0
		i = 0
		while i < len(S):
			if S[i] == '1':
				curr_diff -= 1
				if curr_diff < 0:
					curr_diff = 0
			else:
				curr_diff += 1
				if curr_diff > max_diff:
					max_diff = curr_diff
			i += 1
		if max_diff == 0:
			return -1
		return max_diff


from sys import *

class Solution:

	def maxSubstring(self, s):
		maxi = -maxsize - 1
		s1 = 0
		for i in s:
			if i == '0':
				s1 += 1
			else:
				s1 -= 1
			if s1 < 0:
				s1 = 0
			maxi = max(maxi, s1)
		if maxi == 0:
			return -1
		else:
			return maxi


class Solution:

	def maxSubstring(self, S):
		curr_sum = 0
		ov_sum = -1
		for i in S:
			if i == '1':
				curr_sum = curr_sum - 1
				if curr_sum < 0:
					curr_sum = 0
			else:
				curr_sum = curr_sum + 1
				ov_sum = max(curr_sum, ov_sum)
		return ov_sum


from sys import *

class Solution:

	def maxSubstring(self, S):
		maxi = -maxsize - 1
		su = 0
		for i in S:
			if i == '0':
				su += 1
			else:
				su -= 1
			if su < 0:
				su = 0
			maxi = max(maxi, su)
		if maxi == 0:
			return -1
		else:
			return maxi


class Solution:

	def maxSubstring(self, S):
		n = len(S)
		if S.count('1') == n:
			return -1
		dp = []
		ones = 0
		zeros = 0
		for i in S:
			if i == '0':
				zeros += 1
				if ones > 0:
					dp.append(-ones)
					ones = 0
			else:
				ones += 1
				if zeros > 0:
					dp.append(zeros)
					zeros = 0
		if zeros > 0:
			dp.append(zeros)
		if ones > 0:
			dp.append(-ones)
		curr = 0
		maxi = 0
		for i in dp:
			curr += i
			maxi = max(maxi, curr)
			if curr < 0:
				curr = 0
		return maxi


class Solution:

	def maxSubstring(self, S):
		check = 0
		maximum = 0
		if S == '1' * len(S):
			return -1
		for i in S:
			if i == '1':
				check -= 1
			else:
				check += 1
			if check < 0:
				check = 0
			if maximum < check:
				maximum = check
		return maximum


class Solution:

	def maxSubstring(self, S):
		if '0' not in S:
			return -1
		n = len(S)
		dp = [-1 for i in range(n)]
		for i in range(n):
			if S[i] == '0':
				dp[i] = 1
		maxs = -1
		s = 0
		for i in range(n):
			s += dp[i]
			if s < 0:
				s = 0
			if s > maxs:
				maxs = s
		return maxs


class Solution:

	def maxSubstring(self, S):
		opt = [0 for i in range(len(S))]
		opt[0] = 1 if S[0] == '0' else -1
		for i in range(1, len(S)):
			if S[i] == '1':
				opt[i] = max(-1, opt[i - 1] - 1)
			elif S[i] == '0':
				opt[i] = max(1, opt[i - 1] + 1)
		return max(opt)


class Solution:

	def maxSubstring(self, s):
		n = len(s)
		maxd = float('-inf')
		csum = zc = 0
		for i in range(n):
			if s[i] == '1':
				csum -= 1
			else:
				zc += 1
				csum += 1
			maxd = max(maxd, csum)
			csum = max(csum, 0)
		return maxd if zc else -1


class Solution:

	def maxSubstring(self, S):
		n = len(S)
		maxDifference = float('-inf')
		maxEndingHere = 0
		for i in range(0, n):
			if S[i] == '0':
				maxEndingHere += 1
			else:
				maxEndingHere -= 1
			if maxEndingHere > maxDifference:
				maxDifference = maxEndingHere
			if maxEndingHere < 0:
				maxEndingHere = 0
		return maxDifference


class Solution:

	def maxSubstring(self, s):
		t = 0
		a = []
		d = {}
		for i in range(0, len(s)):
			d[s[i]] = d.get(s[i], 0) + 1
			if d.get('0', 0) > d.get('1', 0):
				t = d.get('0', 0) - d.get('1', 0)
				a.append(t)
			else:
				d['0'] = 0
				d['1'] = 0
		if len(a) == 0:
			return -1
		else:
			return max(a)


class Solution:

	def maxSubstring(self, S):
		max_so_far = 0
		ans = 0
		for i in S:
			if i == '0':
				ans += 1
			else:
				ans -= 1
			if ans < 0:
				ans = 0
			if ans > max_so_far:
				max_so_far = ans
		return max_so_far if max_so_far != 0 else -1


class Solution:

	def maxSubstring(self, S):
		arr = []
		for i in S:
			if i == '1':
				arr.append(-1)
			else:
				arr.append(1)
		sum1 = arr[0]
		res = arr[0]
		for i in range(1, len(arr)):
			sum1 = max(sum1 + arr[i], arr[i])
			res = max(res, sum1)
		return -1 if res == -len(s) else res


class Solution:

	def maxSubstring(self, S):
		n = len(S)
		if S == '1' * n:
			return -1
		i = 0
		maxi = 0
		summ = 0
		while i < n:
			if S[i] == '0':
				summ += 1
			else:
				summ -= 1
			maxi = max(maxi, summ)
			if summ < 0:
				summ = 0
			i += 1
		return maxi


class Solution:

	def maxSubstring(self, S):
		dp = [[0, 0] for i in range(len(S))]
		dp[0][1] = 1 if S[0] == '0' else 0
		dp[0][0] = 0
		for i in range(1, len(S)):
			dp[i][0] = max(dp[i - 1][0], dp[i - 1][1])
			if S[i] == '1':
				a = -1
			else:
				a = 1
			dp[i][1] = max(dp[i - 1][1] + a, 0)
		m = max(dp[-1][0], dp[-1][1])
		if m == 0:
			return -1
		return m


class Solution:

	def maxSubstring(self, S):
		sweep = 0
		ans = -1
		for i in S:
			if i == '0':
				sweep += 1
			else:
				sweep -= 1
			ans = max(ans, sweep)
			if sweep < 0:
				sweep = 0
		return ans


class Solution:

	def maxSubstring(self, S):
		if '0' not in S:
			return -1
		curSum = 0
		nums = []
		for (i, num) in enumerate(S):
			if num == '0':
				nums.append(1)
			else:
				nums.append(-1)
		curSum = 0
		ans = 0
		for num in nums:
			curSum = max(curSum + num, num)
			ans = max(ans, curSum)
		return ans


import sys

class Solution:

	def maxSubstring(self, S):
		ones = 0
		(curr, maxx) = (0, 0)
		for i in range(len(S)):
			if S[i] == '0':
				curr += 1
			elif S[i] == '1':
				curr -= 1
				ones += 1
			maxx = max(curr, maxx)
			if curr < 0:
				curr = 0
		if len(S) == ones:
			return -1
		return maxx


class Solution:

	def maxSubstring(self, S):
		cur_val = 0
		max_arr = int(S[0])
		arr = []
		b = []
		for i in S:
			if i == '1':
				arr.append(-1)
				b.append(True)
			else:
				arr.append(1)
				b.append(False)
		if all(b) == True:
			return -1
		for j in range(len(s)):
			cur_val += arr[j]
			if cur_val > max_arr:
				max_arr = cur_val
			if cur_val < 0:
				cur_val = 0
		return max_arr


class Solution:

	def maxSubstring(self, S):
		CurrSum = 0
		MaxSum = -9999
		ans = []
		for i in range(len(S)):
			if S[i] == '0':
				ans.append(1)
			elif S[i] == '1':
				ans.append(-1)
		for i in range(len(ans)):
			CurrSum += ans[i]
			MaxSum = max(MaxSum, CurrSum)
			if CurrSum < 0:
				CurrSum = 0
		return MaxSum


class Solution:

	def maxSubstring(self, S):
		max_so_far = 0
		max_ending = 0
		k = 0
		for i in range(len(s)):
			if S[i] == '1':
				max_ending -= 1
				k += 1
			else:
				max_ending += 1
			max_so_far = max(max_so_far, max_ending)
			if max_ending < 0:
				max_ending = 0
		return -1 if k == len(S) else max_so_far


class Solution:

	def maxSubstring(self, S):
		maxi = -1
		sumi = 0
		re = 0
		for ele in range(len(S)):
			re = re + int(S[ele])
		if len(S) == re:
			return -1
		for i in range(len(S)):
			if S[i] == '1':
				sumi = sumi - 1
			else:
				sumi = sumi + 1
			if sumi < 0:
				sumi = 0
			maxi = max(maxi, sumi)
		return maxi


class Solution:

	def maxSubstring(self, S):
		m = float('-inf')
		c = 0
		for i in range(len(S)):
			if c < 0:
				c = 0
			if S[i] == '0':
				c += 1
			else:
				c -= 1
			m = max(m, c)
		return m


class Solution:

	def maxSubstring(self, S):
		max_until = 0
		ma = -1000000000.0
		x = 0
		for i in range(len(S)):
			if S[i] == '0':
				max_until += 1
			else:
				max_until += -1
			if max_until > ma:
				ma = max_until
			if max_until < 0:
				max_until = 0
		return ma


class Solution:

	def maxSubstring(self, S):
		maxi = 0
		zero = 0
		one = 0
		diff = 0
		for i in S:
			if i == '0':
				zero += 1
			elif i == '1':
				one += 1
			if one > zero:
				one = zero = 0
			if zero - one > diff:
				diff = zero - one
		if diff == 0:
			return -1
		return diff


class Solution:

	def maxSubstring(self, S):
		max_until = 0
		ma = -1000000000.0
		for i in s:
			if i == '0':
				max_until += 1
			else:
				max_until += -1
			if max_until > ma:
				ma = max_until
			if max_until < 0:
				max_until = 0
		return ma


class Solution:

	def maxSubstring(self, S):
		if '0' not in S:
			return -1
		curr = 0
		maxx = 0
		for i in S:
			if i == '0':
				curr += 1
			else:
				maxx = max(curr, maxx)
				curr -= 1
			if curr < 0:
				curr = 0
		maxx = max(curr, maxx)
		return maxx


class Solution:

	def maxSubstring(self, S):
		output = 0
		maxi = 0
		summa = 0
		for item in S:
			summa += item == '1'
			summa -= item == '0'
			maxi = max(maxi, summa)
			output = max(output, maxi - summa)
		return output if output else -1


class Solution:

	def maxSubstring(self, s):
		n = len(s)
		l1 = []
		i = 0
		while i < n:
			if s[i] == '0':
				c = 0
				while i < n and s[i] == '0':
					c += 1
					i += 1
				l1.append(c)
				i -= 1
			else:
				c = 0
				while i < n and s[i] == '1':
					c += 1
					i += 1
				l1.append(c * -1)
				i -= 1
			i += 1
		if l1[0] == len(s) * -1:
			return -1
		l2 = [x * -1 for x in l1]
		a1 = 0
		a2 = 0
		m = 0
		for i in range(len(l1)):
			m = m + l1[i]
			if a1 < m:
				a1 = m
			if m < 0:
				m = 0
		m = 0
		for i in range(len(l1)):
			m = m + l1[i]
			if a2 < m:
				a2 = m
			if m < 0:
				m = 0
		return max(a2, a1)


class Solution:

	def maxSubstring(self, s):
		ans = -1
		temp = 0
		for i in s:
			if i == '0':
				temp += 1
			else:
				temp -= 1
			ans = max(ans, temp)
			if temp < 0:
				temp = 0
		return ans


class Solution:

	def maxSubstring(self, S):
		ans = -1
		zeros = 0
		for c in S:
			if c == '0':
				zeros += 1
			else:
				zeros -= 1
			ans = max(ans, zeros)
			if zeros < 0:
				zeros = 0
		return ans


class Solution:

	def maxSubstring(self, S):
		currSum = 0
		MaxiSum = -9999
		ans = []
		for i in range(len(S)):
			if S[i] == '0':
				ans.append(1)
			elif S[i] == '1':
				ans.append(-1)
		for i in range(len(S)):
			currSum += int(ans[i])
			if MaxiSum < currSum:
				MaxiSum = currSum
			if currSum < 0:
				currSum = 0
		return MaxiSum


class Solution:

	def maxSubstring(self, S):
		su = 0
		mx = 0
		for i in S:
			if i == '0':
				su += 1
			else:
				su += -1
			if su < 0:
				su = 0
			mx = max(mx, su)
		if mx == 0:
			return -1
		return mx


class Solution:

	def maxSubstring(self, s):
		cursum = 0
		maxsum = 0
		for i in range(len(s)):
			cursum += 1 if s[i] == '0' else -1
			if cursum < 0:
				cursum = 0
			maxsum = max(maxsum, cursum)
		return maxsum if maxsum != 0 else -1


class Solution:

	def maxSubstring(self, S):
		ones = 0
		zeroes = 0
		newArray = list(S)
		for i in range(0, len(S)):
			if newArray[i] == '1':
				newArray[i] = -1
			elif S[i] == '0':
				newArray[i] = 1
		sum = 0
		for (j, i) in enumerate(newArray):
			if sum + i < i:
				sum = i
			else:
				sum = sum + i
			newArray[j] = sum
		return max(newArray)


class Solution:

	def maxSubstring(self, S):
		dp = [0 for i in range(len(S))]
		no_of_zeroes = 0
		no_of_ones = 0
		for i in range(len(S)):
			if S[i] == '1':
				no_of_ones += 1
			elif no_of_zeroes < no_of_ones:
				no_of_zeroes = 1
				no_of_ones = 0
			else:
				no_of_zeroes += 1
			dp[i] = no_of_zeroes - no_of_ones
		return max(dp) if max(dp) > 0 else -1


class Solution:

	def maxSubstring(self, S):
		n = len(S)
		curr = maxi = 0
		for i in range(n):
			if S[i] == '1':
				curr -= 1
			else:
				curr += 1
			maxi = max(curr, maxi)
			if curr < 0:
				curr = 0
		if not maxi:
			return -1
		return maxi


class Solution:

	def maxSubstring(self, S):
		s = list(S)
		for i in range(len(s)):
			if s[i] == '1':
				s[i] = -1
			else:
				s[i] = 1
		summ = 0
		ans = 0
		for i in range(len(s)):
			summ += s[i]
			ans = max(ans, summ)
			if summ < 0:
				summ = 0
		if max(s) < 0:
			return max(s)
		return ans


class Solution:

	def maxSubstring(self, s):
		curr = 0
		ans = float('-inf')
		for (ind, val) in enumerate(s):
			if val == '1':
				curr -= 1
			else:
				curr += 1
			ans = max(ans, curr)
			if curr < 0:
				curr = 0
		return ans


from math import inf

class Solution:

	def maxSubstring(self, s):
		trans_num = -1
		curr_max_sum = 0
		global_max_sum = -inf
		for ch in s:
			trans_num = -1
			if ch == '0':
				trans_num = 1
			if curr_max_sum + trans_num < trans_num:
				curr_max_sum = trans_num
			else:
				curr_max_sum += trans_num
			global_max_sum = max(global_max_sum, curr_max_sum)
		return global_max_sum


class Solution:

	def maxSubstring(self, S):
		(zero, ans) = (0, 0)
		for i in range(len(S)):
			if S[i] == '1':
				zero -= 1
			else:
				zero += 1
			ans = max(ans, zero)
			if zero < 0:
				zero = 0
		if not ans:
			return -1
		return ans


class Solution:

	def maxSubstring(self, S):
		n = len(S)
		count = maxi = 0
		for i in range(n):
			if S[i] == '0':
				count += 1
			else:
				count -= 1
			if count < 0:
				count = 0
			if maxi < count:
				maxi = count
		if maxi == 0:
			return -1
		return maxi


class Solution:

	def maxSubstring(self, S):
		curMax = 0
		maxSum = -2
		for i in S:
			curMax += 1 if i == '0' else -1
			if curMax < 0:
				curMax = 0
			maxSum = max(curMax, maxSum)
		return maxSum if maxSum else -1


class Solution:

	def maxSubstring(self, S):
		s = []
		for i in range(len(S)):
			s.append(int(S[i]))
			if s[i] == 0:
				s[i] = 1
			else:
				s[i] = -1
		if 1 not in s:
			return -1
		max_ = 0
		max_t = 0
		for i in range(len(s)):
			max_t += s[i]
			if max_t > max_:
				max_ = max_t
			if max_t < 0:
				max_t = 0
		return max_


class Solution:

	def maxSubstring(self, S):
		sum = 0
		maxi = -1000000000.0
		n = len(S)
		for i in range(n):
			x = 1 if S[i] == '0' else -1
			sum += x
			maxi = max(maxi, sum)
			if sum < 0:
				sum = 0
		return maxi


class Solution:

	def maxSubstring(self, S):
		nums = []
		for i in S:
			if i == '0':
				nums.append(1)
			else:
				nums.append(-1)
		sum = 0
		maxi = -1000000000.0
		for i in range(len(nums)):
			sum += nums[i]
			maxi = max(maxi, sum)
			if sum < 0:
				sum = 0
		return maxi


class Solution:

	def maxSubstring(self, S):
		zeros = 0
		ones = 0
		max_diff = -100000
		curr = 0
		while curr < len(S):
			if S[curr] == '0':
				zeros += 1
			else:
				ones += 1
			max_diff = max(max_diff, zeros - ones)
			if zeros - ones < 0:
				zeros = 0
				ones = 0
			curr += 1
		return max_diff


class Solution:

	def maxSubstring(self, S):
		l = []
		cur = 0
		max_s = 0
		for i in range(len(S)):
			if S[i] == '0':
				l.append(1)
			else:
				l.append(-1)
		for i in l:
			cur += i
			if cur >= max_s:
				max_s = cur
			elif cur < max_s and cur > 0:
				pass
			else:
				cur = 0
		if max_s == 0:
			return -1
		else:
			return max_s


class Solution:

	def maxSubstring(self, S):
		flag = False
		n = len(S)
		for ele in S:
			if ele == '0':
				flag = True
				break
		if flag == False:
			return -1
		maxsum = 0
		temp = 0
		for i in range(n):
			if S[i] == '1':
				temp += -1
			else:
				temp += 1
			maxsum = max(maxsum, temp)
			if temp < 0:
				temp = 0
		return maxsum


class Solution:

	def maxSubstring(self, S):
		sample = ''
		for i in range(len(s)):
			if s[i] == '0':
				sample += '1'
			else:
				sample += '0'
		curr = 0
		max_curr = 0
		for i in range(len(s)):
			if sample[i] == '0':
				curr -= 1
			if sample[i] == '1':
				curr += 1
			if curr > max_curr:
				max_curr = curr
			if curr < 0:
				curr = 0
		if max_curr == 0:
			return -1
		else:
			return max_curr


class Solution:

	def maxSubstring(self, S):
		c = 0
		m = 0
		for i in S:
			if i == '0':
				c = c + 1
			else:
				c = c - 1
			if c < 0:
				c = 0
			m = max(m, c)
		if m == 0:
			return -1
		else:
			return m


class Solution:

	def maxSubstring(self, s):
		n = len(s)
		dp = [[0, 0] for x in range(n)]
		if s[0] == '1':
			dp[0][1] = 1
		else:
			dp[0][0] = 1
		maxi = dp[0][0] - dp[0][1]
		for i in range(1, n):
			a = 0
			b = 0
			t1 = dp[i - 1][0]
			t2 = dp[i - 1][1]
			if s[i] == '1':
				b += 1
				t2 += 1
			else:
				a += 1
				t1 += 1
			if a - b > t1 - t2:
				dp[i][0] = a
				dp[i][1] = b
			else:
				dp[i][0] = t1
				dp[i][1] = t2
			maxi = max(maxi, dp[i][0] - dp[i][1])
		return maxi


class Solution:

	def maxSubstring(self, S):
		ans = 0
		s = 0
		S = str(S)
		if S == '1' * len(S):
			return -1
		for i in S:
			if i == '0':
				s += 1
			else:
				s -= 1
			if s < 0:
				s = 0
			ans = max(ans, s)
		return ans


class Solution:

	def maxSubstring(self, s):
		c = 0
		n = len(s)
		for i in s:
			if i == '0':
				break
			c += 1
		if c == n:
			return -1
		r = 0
		z = False
		o = False
		res = r
		for i in range(n):
			if s[i] == '0':
				r += 1
			else:
				r -= 1
				o = True
			if r < 0:
				r = 0
				o = False
			res = max(res, r)
		return res


class Solution:

	def maxSubstring(self, S):
		num_arr = [int(ch) for ch in S]
		if sum(num_arr) == len(S):
			return -1
		max_ending_here = 0
		max_so_far = 0
		for ch in S:
			if ch == '1':
				max_ending_here -= 1
			else:
				max_ending_here += 1
			max_so_far = max(max_so_far, max_ending_here)
			if max_ending_here < 0:
				max_ending_here = 0
		return max_so_far


class Solution:

	def maxSubstring(self, S):
		one_counter = 0
		zero_counter = 0
		sum_val = 0
		max_val = 0
		for _ in S:
			if _ == '1':
				one_counter += 1
			else:
				zero_counter += 1
			sum_val = zero_counter - one_counter
			max_val = max(max_val, sum_val)
			if sum_val < 0:
				one_counter -= 1
		if zero_counter == 0:
			return -1
		return max_val


class Solution:

	def maxSubstring(self, s):
		ans = -1
		cans = 0
		for i in range(len(s)):
			if s[i] == '1':
				cans -= 1
			else:
				cans += 1
			ans = max(ans, cans)
			cans = max(0, cans)
		return ans


class Solution:

	def maxSubstring(self, S):
		S = list(S)
		for i in range(len(S)):
			if S[i] == '0':
				S[i] = 1
			else:
				S[i] = -1
		cur = 0
		maxi = float('-inf')
		for i in S:
			cur += i
			maxi = max(maxi, cur)
			if cur < 0:
				cur = 0
		return maxi


class Solution:

	def maxSubstring(self, S):
		maxsum = 0
		cursum = 0
		S = list(map(int, list(S)))
		for x in S:
			cursum += 1 if x == 0 else -1
			if cursum < 0:
				cursum = 0
			maxsum = max(maxsum, cursum)
		return maxsum if maxsum else -1


class Solution:

	def maxSubstring(self, S):
		currentSum = 0
		maxSum = 0
		for i in range(0, len(S)):
			currentSum += 1 if S[i] == '0' else -1
			if currentSum < 0:
				currentSum = 0
			maxSum = max(maxSum, currentSum)
		return maxSum if maxSum else -1


class Solution:

	def maxSubstring(self, S):
		dp = [0 for i in range(len(S))]
		zeros = 0
		ones = 0
		for i in range(len(S)):
			if S[i] == '1':
				ones += 1
			if S[i] == '0':
				if zeros < ones:
					zeros = 1
					ones = 0
				else:
					zeros += 1
			dp[i] = zeros - ones
		ans = max(dp)
		if ans < 0:
			return -1
		return ans