Problem Statement

Given a binary string 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

Problem Link

Maximum difference of zeros and ones in binary string | Practice | GeeksforGeeks

Approach

Assume '0' as 1 and '1' as -1, then apply Kadane’s algorithm

Code

class Solution{
public:	
	int maxSubstring(string S)
	{
	    int n = S.size();
	    vector<int> v(n);
	    
	    for(int i=0;i<n;i++)
	    v[i] = S[i]=='0' ? 1 : -1;
	    
	    int gm=v[0],lm=v[0];
	    
	    for(int i=1;i<n;i++)
	    {
	        lm = max(v[i],lm+v[i]);
	        gm = max(lm,gm);
	    }
	    return gm<0 ? -1 : gm;
	}
};

Time complexity O(n)