Count Substrings with equal number of 0s, 1s and 2s
Given a string that consists of only 0s, 1s and 2s, count the number of substrings that have an equal number of 0s, 1s, and 2s.
Examples:
Input: str = “0102010”
Output: 2
Explanation: Substring str[2, 4] = “102” and substring str[4, 6] = “201” has equal number of 0, 1 and 2Input: str = “102100211”
Output: 5
Brute Force: To solve the problem using this approach follow the below idea:
Iterate through all substrings of str using nested loops and check whether they contain equal 0,1 and 2 or not.
C++
// C++ program to find substring with equal // number of 0's, 1's and 2's #include <bits/stdc++.h> using namespace std; // Method to count number of substring which // has equal 0, 1 and 2 long long getSubstringWithEqual012(string s) { vector<string> arr; int n = s.size(); //generating subarrays for ( int i=0;i<n;i++) { for ( int j=i;j<n;j++) { string s1 = "" ; for ( int k=i;k<=j;k++) { s1+=s[k]; } arr.push_back(s1); } } int count = 0; int countZero,countOnes,countTwo; // iterating over array of all substrings for ( int i=0;i<arr.size();i++) { countZero=0; countOnes=0; countTwo=0; string curs = arr[i]; for ( int j=0;j<curs.size();j++) { if (curs[j] == '0' ) countZero++; if (curs[j] == '1' ) countOnes++; if (curs[j] == '2' ) countTwo++; } // if number of ones,two and zero are equal in a substring if (countZero == countOnes and countOnes == countTwo) { count++; } } return count; } // Driver's code int main() { string str = "0102010" ; // Function call cout << getSubstringWithEqual012(str) << endl; return 0; } // This code is contributed by Arpit Jain |
Java
// Java program to find substring with equal // number of 0's, 1's and 2's import java.util.*; public class GFG { // Method to count number of substring which // has equal 0, 1 and 2 static long getSubstringWithEqual012(String s) { ArrayList<String> arr = new ArrayList<>(); int n = s.length(); // generating subarrays for ( int i = 0 ; i < n; i++) { for ( int j = i; j < n; j++) { String s1 = "" ; for ( int k = i; k <= j; k++) { s1 += s.charAt(k); } arr.add(s1); } } int count = 0 ; int countZero, countOnes, countTwo; // iterating over array of all substrings for ( int i = 0 ; i < arr.size(); i++) { countZero = 0 ; countOnes = 0 ; countTwo = 0 ; String curs = arr.get(i); for ( int j = 0 ; j < curs.length(); j++) { if (curs.charAt(j) == '0' ) countZero++; if (curs.charAt(j) == '1' ) countOnes++; if (curs.charAt(j) == '2' ) countTwo++; } // if number of ones,two and zero are equal in a // substring if (countZero == countOnes && countOnes == countTwo) { count++; } } return count; } // Driver's code public static void main(String[] args) { String str = "0102010" ; System.out.println(getSubstringWithEqual012(str)); } } // This code is contributed by Karandeep1234 |
Python3
# Python3 program to find subString with equal # number of 0's, 1's and 2's # Method to count number of subString which # has equal 0, 1 and 2 def getSubStringWithEqual012(s) : arr = []; n = len (s); # generating subarrays for i in range (n): for j in range (i, n): s1 = "" for k in range (i, 1 + j): s1 + = s[k]; arr.append(s1); count = 0 ; # iterating over array of all subStrings for i in range ( len (arr)): countZero = 0 ; countOnes = 0 ; countTwo = 0 ; curs = arr[i]; for j in range ( len (curs)): if (curs[j] = = '0' ): countZero + = 1 ; if (curs[j] = = '1' ): countOnes + = 1 ; if (curs[j] = = '2' ): countTwo + = 1 ; # if number of ones,two and zero are equal in a subString if (countZero = = countOnes and countOnes = = countTwo): count + = 1 ; return count; # Driver's code Str = "0102010" ; # Function call print (getSubStringWithEqual012( Str )); # This code is contributed by phasing17 |
C#
// C# program to find substring with equal // number of 0's, 1's and 2's using System; using System.Collections; using System.Collections.Generic; public class GFG { // Method to count number of substring which // has equal 0, 1 and 2 static long getSubstringWithEqual012( string s) { List< string > arr = new List< string >(); int n = s.Length; // generating subarrays for ( int i = 0; i < n; i++) { for ( int j = i; j < n; j++) { String s1 = "" ; for ( int k = i; k <= j; k++) { s1 += s[k]; } arr.Add(s1); } } int count = 0; int countZero, countOnes, countTwo; // iterating over array of all substrings for ( int i = 0; i < arr.Count; i++) { countZero = 0; countOnes = 0; countTwo = 0; String curs = arr[i]; for ( int j = 0; j < curs.Length; j++) { if (curs[j] == '0' ) countZero++; if (curs[j] == '1' ) countOnes++; if (curs[j] == '2' ) countTwo++; } // if number of ones,two and zero are equal in a // substring if (countZero == countOnes && countOnes == countTwo) { count++; } } return count; } // Driver's code public static void Main( string [] args) { string str = "0102010" ; Console.WriteLine(getSubstringWithEqual012(str)); } } // This code is contributed by Karandeep1234 |
Javascript
// JS program to find substring with equal // number of 0's, 1's and 2's // Method to count number of substring which // has equal 0, 1 and 2 function getSubstringWithEqual012(s) { let arr = []; let n = s.length; //generating subarrays for ( var i=0;i<n;i++) { for ( var j=i;j<n;j++) { var s1 = "" ; for ( var k=i;k<=j;k++) { s1+=s[k]; } arr.push(s1); } } var count = 0; var countZero,countOnes,countTwo; // iterating over array of all substrings for ( var i=0;i<arr.length;i++) { countZero=0; countOnes=0; countTwo=0; var curs = arr[i]; for ( var j=0;j<curs.length;j++) { if (curs[j] == '0 ') countZero++; if(curs[j] == ' 1 ') countOnes++; if(curs[j] == ' 2 ') countTwo++; } // if number of ones,two and zero are equal in a substring if(countZero == countOnes && countOnes == countTwo) { count++; } } return count; } // Driver' s code let str = "0102010" ; // Function call console.log(getSubstringWithEqual012(str)); // This code is contributed by phasing17 |
2
Time Complexity: O(N3)
Auxiliary Space: O(1)
Count Substrings with equal number of 0s, 1s and 2s using Hashing:
Traverse through the string and keep track of counts of 0, 1, and 2 and make a difference pair of (zeroes – ones, zeroes – twos) and increase the answer count if this difference pair is seen before and at every index increase the count of this difference pair in the map
Follow the given steps to solve the problem:
- Declare a map to store the difference pair and three variables to store the count of 0’s, 1’s and 2’s
- Traverse the string and keep track of the count of 0’s, 1’s, and 2’s
- At each index make a difference pair of (zeroes – ones, zeroes – twos)
- Using the map check if this pair is seen before, if it is so then increase the result count
- Then, increase the count of this pair in the map
- Return the result
Below is the implementation of the above approach:
C++
// C++ program to find substring with equal // number of 0's, 1's and 2's #include <bits/stdc++.h> using namespace std; // Method to count number of substring which // has equal 0, 1 and 2 int getSubstringWithEqual012(string str) { int N = str.length(); // map to store, how many times a difference // pair has occurred previously map<pair< int , int >, int > mp; mp[make_pair(0, 0)] = 1; // zc (Count of zeroes), oc(Count of 1s) // and tc(count of twos) // In starting all counts are zero int zc = 0, oc = 0, tc = 0; // looping into string int res = 0; // Initialize result for ( int i = 0; i < N; ++i) { // increasing the count of current character if (str[i] == '0' ) zc++; else if (str[i] == '1' ) oc++; else tc++; // Assuming that string doesn't contain // other characters // making pair of differences (z[i] - o[i], // z[i] - t[i]) pair< int , int > tmp = make_pair(zc - oc, zc - tc); // Count of previous occurrences of above pair // indicates that the subarrays forming from // every previous occurrence to this occurrence // is a subarray with equal number of 0's, 1's // and 2's res = res + mp[tmp]; // Increasing the count of current difference // pair by 1 mp[tmp]++; } return res; } // Driver's code int main() { string str = "0102010" ; // Function call cout << getSubstringWithEqual012(str) << endl; return 0; } |
Java
// Java program to find substring with equal // number of 0's, 1's and 2's import java.io.*; import java.util.*; class GFG { // Method to count number of substring which // has equal 0, 1 and 2 private static int getSubstringWithEqual012(String str) { // map to store, how many times a difference // pair has occurred previously (key = diff1 * // diff2) HashMap<String, Integer> map = new HashMap<>(); map.put( "0*0" , 1 ); // zc (Count of zeroes), oc(Count of 1s) // and tc(count of twos) // In starting all counts are zero int zc = 0 , oc = 0 , tc = 0 ; int ans = 0 ; // looping into string for ( int i = 0 ; i < str.length(); i++) { // Increasing the count of current character if (str.charAt(i) == '0' ) zc++; else if (str.charAt(i) == '1' ) oc++; else tc++; // making key of differences (z[i] - o[i], // z[i] - t[i]) String key = (zc - oc) + "*" + (zc - tc); // Count of previous occurrences of above pair // indicates that the subarrays forming from // every previous occurrence to this occurrence // is a subarray with equal number of 0's, 1's // and 2's ans += map.getOrDefault(key, 0 ); map.put(key, map.getOrDefault(key, 0 ) + 1 ); } // increasing the count of current difference // pair by 1 return ans; } // Driver's Code public static void main(String[] args) { String str = "0102010" ; // Function call System.out.println(getSubstringWithEqual012(str)); } } |
Python3
# Python3 program to find substring with equal # number of 0's, 1's and 2's # Method to count number of substring which # has equal 0, 1 and 2 def getSubstringWithEqual012(string): N = len (string) # map to store, how many times a difference # pair has occurred previously mp = dict () mp[( 0 , 0 )] = 1 # zc (Count of zeroes), oc(Count of 1s) # and tc(count of twos) # In starting all counts are zero zc, oc, tc = 0 , 0 , 0 # looping into string res = 0 # Initialize result for i in range (N): # increasing the count of current character if string[i] = = '0' : zc + = 1 elif string[i] = = '1' : oc + = 1 else : tc + = 1 # Assuming that string doesn't contain # other characters # making pair of differences (z[i] - o[i], # z[i] - t[i]) tmp = (zc - oc, zc - tc) # Count of previous occurrences of above pair # indicates that the subarrays forming from # every previous occurrence to this occurrence # is a subarray with equal number of 0's, 1's # and 2's if tmp not in mp: res + = 0 else : res + = mp[tmp] # increasing the count of current difference # pair by 1 if tmp in mp: mp[tmp] + = 1 else : mp[tmp] = 1 return res # Driver's Code if __name__ = = "__main__" : string = "0102010" print (getSubstringWithEqual012(string)) # This code is contributed by # sanjeev2552 |
C#
// C# program to implement the approach using System; using System.Collections.Generic; class GFG { // Method to count number of substring which // has equal 0, 1 and 2 private static int getSubstringWithEqual012( string str) { // dictionary to store, how many times a difference // pair has occurred previously (key = diff1 * // diff2) Dictionary< string , int > map = new Dictionary< string , int >(); map.Add( "0*0" , 1); // zc (Count of zeroes), oc(Count of 1s) // and tc(count of twos) // In starting all counts are zero int zc = 0, oc = 0, tc = 0; int ans = 0; // looping into string for ( int i = 0; i < str.Length; i++) { // Increasing the count of current character if (str[i] == '0' ) zc++; else if (str[i] == '1' ) oc++; else tc++; // making key of differences (z[i] - o[i], // z[i] - t[i]) string key = (zc - oc) + "*" + (zc - tc); // Count of previous occurrences of above pair // indicates that the subarrays forming from // every previous occurrence to this occurrence // is a subarray with equal number of 0's, 1's // and 2's if (map.ContainsKey(key)) ans += map[key]; else map.Add(key, 1); } // returning the count of subarray with equal // number of 0's, 1's and 2's return ans; } // Driver's Code public static void Main( string [] args) { string str = "0102010" ; // Function call Console.WriteLine(getSubstringWithEqual012(str)); } } |
Javascript
function getSubstringWithEqual012(string) { const N = string.length; // map to store, how many times a difference pair has occurred previously const mp = {}; mp[[0, 0]] = 1; // zc (Count of zeroes), oc(Count of 1s) and tc(count of twos) // In starting all counts are zero let zc = 0, oc = 0, tc = 0; // looping into string let res = 0; // Initialize result for (let i = 0; i < N; i++) { // increasing the count of current character if (string[i] === '0' ) { zc += 1; } else if (string[i] === '1' ) { oc += 1; } else { tc += 1; // Assuming that string doesn't contain other characters } // making pair of differences (z[i] - o[i], z[i] - t[i]) const tmp = [zc - oc, zc - tc]; // Count of previous occurrences of above pair // indicates that the subarrays forming from // every previous occurrence to this occurrence is a // subarray with equal number of 0's, 1's // and 2's if (!mp.hasOwnProperty(tmp)) { res += 0; } else { res += mp[tmp]; } // increasing the count of current difference pair by 1 if (mp.hasOwnProperty(tmp)) { mp[tmp] += 1; } else { mp[tmp] = 1; } } return res; } // Driver's Code console.log(getSubstringWithEqual012( "0102010" )); |
2
Time Complexity: O(N * log N)
Auxiliary Space: O(N)
Contact Us