Length of the longest substring with equal 1s and 0s
Given a binary string. We need to find the length of the longest balanced substring. A substring is balanced if it contains an equal number of 0 and 1.
Examples:
Input : input = 110101010
Output : Length of longest balanced sub string = 8Input : input = 0000
Output : Length of longest balanced sub string = 0
A simple solution is to use two nested loops to generate every substring. And a third loop to count number of 0s and 1s in current substring.
Below is the implementation of the above approach:
C++
// C++ program to find the length of // the longest balanced substring #include <bits/stdc++.h> using namespace std; // Function to check if a string contains // equal number of one and zeros or not bool isValid(string p) { int n = p.length(); int c1 = 0, c0 = 0; for ( int i = 0; i < n; i++) { if (p[i] == '0' ) c0++; if (p[i] == '1' ) c1++; } return (c0 == c1) ? true : false ; } // Function to find the length of // the longest balanced substring int longestSub(string s) { int max_len = 0; int n = s.length(); for ( int i = 0; i < n; i++) { for ( int j = i; j < n; j++) { if (isValid(s.substr(i, j - i + 1)) && max_len < j - i + 1) max_len = j - i + 1; } } return max_len; } // Driver code int main() { string s = "101001000" ; // Function call cout << longestSub(s); return 0; } // This code is contributed by Aditya Kumar (adityakumar129) |
Java
// Java program to find the length of // the longest balanced substring import java.io.*; import java.util.*; class GFG { // Function to check if a string contains // equal number of one and zeros or not public static boolean isValid(String p) { int n = p.length(); int c1 = 0 , c0 = 0 ; for ( int i = 0 ; i < n; i++) { if (p.charAt(i) == '0' ) { c0++; } if (p.charAt(i) == '1' ) { c1++; } } if (c0 == c1) { return true ; } else { return false ; } } // Function to find the length of // the longest balanced substring public static int longestSub(String s) { int max_len = 0 ; int n = s.length(); for ( int i = 0 ; i < n; i++) { for ( int j = i; j < n; j++) { if (isValid(s.substring(i, j + 1 )) && max_len < j - i + 1 ) { max_len = j - i + 1 ; } } } return max_len; } // Driver code public static void main (String[] args) { String s = "101001000" ; // Function call System.out.println(longestSub(s)); } } // This code is contributed by avanitrachhadiya2155 |
Python3
# Python3 program to find the length of # the longest balanced substring # Function to check if a contains # equal number of one and zeros or not def isValid(p): n = len (p) c1 = 0 c0 = 0 for i in range (n): if (p[i] = = '0' ): c0 + = 1 if (p[i] = = '1' ): c1 + = 1 if (c0 = = c1): return True else : return False # Function to find the length of # the longest balanced substring def longestSub(s): max_len = 0 n = len (s) for i in range (n): for j in range (i, n): if (isValid(s[i : j - i + 1 ]) and max_len < j - i + 1 ): max_len = j - i + 1 return max_len # Driver code if __name__ = = '__main__' : s = "101001000" # Function call print (longestSub(s)) # This code is contributed by mohit kumar 29 |
C#
// C# program to find the length of // the longest balanced substring using System; class GFG{ // Function to check if a string contains // equal number of one and zeros or not static bool isValid( string p) { int n = p.Length; int c1 = 0, c0 = 0; for ( int i = 0; i < n; i++) { if (p[i] == '0' ) { c0++; } if (p[i] == '1' ) { c1++; } } if (c0 == c1) { return true ; } else { return false ; } } // Function to find the length of // the longest balanced substring public static int longestSub( string s) { int max_len = 0; int n = s.Length; for ( int i = 0; i < n; i++) { for ( int j = i; j < n; j++) { if (isValid(s.Substring(i, j - i + 1)) && max_len < j - i + 1) { max_len = j - i + 1; } } } return max_len; } // Driver code static public void Main() { string s = "101001000" ; // Function call Console.WriteLine(longestSub(s)); } } // This code is contributed by rag2127 |
Javascript
<script> // Javascript program to find the length of // the longest balanced substring // Function to check if a string contains // equal number of one and zeros or not function isValid(p) { var n = p.length; var c1 = 0, c0 = 0; for ( var i =0; i < n; i++) { if (p[i] == '0' ) c0++; if (p[i] == '1' ) c1++; } return (c0 == c1) ? true : false ; } // Function to find the length of // the longest balanced substring function longestSub(s) { var max_len = 0; var n = s.length; for ( var i = 0; i < n; i++) { for ( var j = i; j < n; j++) { if (isValid(s.substr(i, j - i + 1)) && max_len < j - i + 1) max_len = j - i + 1; } } return max_len; } // Driver code var s = "101001000" ; // Function call document.write( longestSub(s)); </script> |
Output
6
Time Complexity: O(N3)
Auxiliary Space: O(1)
An efficient solution is to use hashing.
- Traverse string and keep track of counts of 1s and 0s as count_1 and count_0 respectively.
- See if current difference between two counts has appeared before (We use hashing to store all differences and first index where a difference appears). If yes, then substring from previous appearance and current index has same number of 0s and 1s.
Below is the implementation of above approach.
C++
// C++ for finding length of longest balanced // substring #include<bits/stdc++.h> using namespace std; // Returns length of the longest substring // with equal number of zeros and ones. int stringLen(string str) { // Create a map to store differences // between counts of 1s and 0s. map< int , int > m; // Initially difference is 0. m[0] = -1; int count_0 = 0, count_1 = 0; int res = 0; for ( int i=0; i<str.size(); i++) { // Keeping track of counts of // 0s and 1s. if (str[i] == '0' ) count_0++; else count_1++; // If difference between current counts // already exists, then substring between // previous and current index has same // no. of 0s and 1s. Update result if this // substring is more than current result. if (m.find(count_1 - count_0) != m.end()) res = max(res, i - m[count_1 - count_0]); // If current difference is seen first time. else m[count_1 - count_0] = i; } return res; } // driver function int main() { string str = "101001000" ; cout << "Length of longest balanced" " sub string = " ; cout << stringLen(str); return 0; } |
Java
// Java Code for finding the length of // the longest balanced substring import java.io.*; import java.util.*; public class MAX_LEN_0_1 { public static void main(String args[]) throws IOException { String str = "101001000" ; // Create a map to store differences //between counts of 1s and 0s. HashMap<Integer,Integer> map = new HashMap<Integer,Integer>(); // Initially difference is 0; map. put( 0 , - 1 ); int res = 0 ; int count_0 = 0 , count_1 = 0 ; for ( int i= 0 ; i<str.length();i++) { // Keep track of count of 0s and 1s if (str.charAt(i)== '0' ) count_0++; else count_1++; // If difference between current counts // already exists, then substring between // previous and current index has same // no. of 0s and 1s. Update result if this // substring is more than current result. if (map.containsKey(count_1-count_0)) res = Math.max(res, (i - map.get(count_1-count_0))); // If the current difference is seen first time. else map.put(count_1-count_0,i); } System.out.println( "Length of longest balanced sub string = " +res); } } |
Python3
# Python3 code for finding length of # longest balanced substring # Returns length of the longest substring # with equal number of zeros and ones. def stringLen( str ): # Create a python dictionary to store # differences between counts of 1s and 0s. m = dict () # Initially difference is 0. m[ 0 ] = - 1 count_0 = 0 count_1 = 0 res = 0 for i in range ( len ( str )): # Keeping track of counts of # 0s and 1s. if str [i] = = '0' : count_0 + = 1 else : count_1 + = 1 # If difference between current # counts already exists, then # substring between previous and # current index has same no. of # 0s and 1s. Update result if # this substring is more than # current result. if m.get(count_1 - count_0)! = None : res = max (res, i - m[count_1 - count_0]) # If current difference is # seen first time. else : m[count_1 - count_0] = i return res # driver code str = "101001000" print ( "Length of longest balanced" " sub string = " ,stringLen( str )) # This code is contributed by "Sharad_Bhardwaj" |
C#
// C# Code for finding the length of // the longest balanced substring using System; using System.Collections.Generic; class GFG { public static void Main( string [] args) { string str = "101001000" ; // Create a map to store differences //between counts of 1s and 0s. Dictionary< int , int > map = new Dictionary< int , int >(); // Initially difference is 0; map[0] = -1; int res = 0; int count_0 = 0, count_1 = 0; for ( int i = 0; i < str.Length;i++) { // Keep track of count of 0s and 1s if (str[i] == '0' ) { count_0++; } else { count_1++; } // If difference between current counts // already exists, then substring between // previous and current index has same // no. of 0s and 1s. Update result if this // substring is more than current result. if (map.ContainsKey(count_1 - count_0)) { res = Math.Max(res, (i - map[count_1 - count_0])); } // If the current difference is // seen first time. else { map[count_1 - count_0] = i; } } Console.WriteLine( "Length of longest balanced" + " sub string = " + res); } } // This code is contributed by Shrikant13 |
Javascript
<script> // Javascript Code for finding the length of // the longest balanced substring let str = "101001000" ; // Create a map to store differences // between counts of 1s and 0s. let map = new Map(); // Initially difference is 0; map.set(0, -1); let res =0; let count_0 = 0, count_1 = 0; for (let i=0; i<str.length;i++) { // Keep track of count of 0s and 1s if (str[i]== '0' ) count_0++; else count_1++; // If difference between current counts // already exists, then substring between // previous and current index has same // no. of 0s and 1s. Update result if this // substring is more than current result. if (map.has(count_1-count_0)) res = Math.max(res, (i - map.get(count_1-count_0))); // If the current difference // is seen first time. else map.set(count_1-count_0,i); } document.write( "Length of longest balanced sub string = " +res ); // This code is contributed by unknown2108 </script> |
Output
Length of longest balanced sub string = 6
Time Complexity: O(n)
Auxiliary Space: O(n)
Extended Problem: Largest subarray with equal number of 0s and 1s