//{ Driver Code Starts //Initial Template for Java import java.io.*; import java.util.*; class GFG { public static void main(String args[]) throws IOException { BufferedReader read = new BufferedReader(new InputStreamReader(System.in)); int t = Integer.parseInt(read.readLine()); while (t-- > 0) { String s = read.readLine(); Solution ob = new Solution(); System.out.println(ob.maxSubstring(s)); } } } // } Driver Code Ends //User function Template for Java class Solution { int maxSubstring(String s) { /* Q52 of dp playlist , making 0's to 1 and 1's to -1 and then applying kadane's algo to find max sum sub array which will also give use the max difference between 0's and 1's */ //applying kadanes int csum = 0 , omax = Integer.MIN_VALUE; for(int i =0 ; i < s.length() ; i++){ char ch = s.charAt(i); int val = 0; if(ch == '0') val = 1; else val = -1; if(csum > 0) csum += val; else csum = val; omax = Math.max(csum , omax); } return omax; } }