Count substrings consisting of equal number of a, b, c and d
Given a string str, the task is to count non-empty substrings with equal number of βaβ, βbβ, βcβ, and βdβ.
Examples:
Input: str = βabcdefβ
Output: 6
Explanation:
Substring consisting of equal number of βaβ, βbβ, βcβ, and βdβ are { βabcdβ, βabcdeβ, βabcdfβ, βabcdefβ, βeβ, βfβ }.
Therefore, the required output is 6.Input: str = βabddcdcβ
Output: 0
Approach: The problem can be solved using Hashing. The idea is to based on the following observations:
If the frequency of the characters { βaβ, βbβ, βcβ, βdβ } in the substring {str[0], β¦, str[i] } is { p, q, r, s} and in the substring {str[0], β¦, str[j] } is { p + x, q + x, r + x, s + x }, then the substring { str[i], β¦, str[j] } must contain equal number of βaβ, βbβ, βcβ, and βdβ.
Follow the steps below to solve the problem:
- Initialize a variable, say cntSub, to store the count of substrings with equal number of βaβ, βbβ, βcβ, βdβ.
- Initialize a Map, say mp, to store the relative frequency of the characters { βaβ, βbβ, βcβ, βdβ }.
If the frequency of the characters βaβ, βbβ, βcβ, and βdβ are { p, q, r, s }, then the relative frequency of the characters are { p β y, q β y, r β y, s β y }, where y = min({p, q, r, s})
- Iterate over the characters of the string and store the relative frequency of the characters βaβ, βbβ, βcβ, and βdβ.
- Traverse the map using key value of the map as i, and for every key value, increment the value of cntSub by .
- Finally, print the value of cntSub.
Below is the implementation of the above approach:
C++
// C++ program to implement // the above approach #include <bits/stdc++.h> using namespace std; // Function to count the substring with // equal number of a, b, c and d int countSubstrings(string str) { // Stores relative frequency of // the characters {'a', 'b', 'c', 'd'} map<pair<pair< int , int >, pair< int , int > >, int > mp; // Initially, frequencies of // 'a', 'b', 'c' and 'd' are 0. mp[{ { 0, 0 }, { 0, 0 } }]++; // Stores relative // frequency of 'a' int p = 0; // Stores relative // frequency of 'b' int q = 0; // Stores relative // frequency of 'c' int r = 0; // Stores relative // frequency of 'd' int s = 0; // Stores count of substring with equal // number of 'a', 'b', 'c' and 'd' int cntSub = 0; // Iterate over the characters // of the string for ( int i = 0; i < str.length(); i++) { // If current character // is 'a' if (str[i] == 'a' ) { // Update p p++; // Stores minimum // of { p, q, r, s} int Y = min(min(s, r), min(p, q)); // Update p p -= Y; // Update q q -= Y; // Update r r -= Y; // Update s s -= Y; } // If current character is b else if (str[i] == 'b' ) { // Update q q++; // Stores minimum // of { p, q, r, s} int Y = min(min(p, q), min(r, s)); // Update p p -= Y; // Update q q -= Y; // Update r r -= Y; // Update s s -= Y; } else if (str[i] == 'c' ) { // Update r r++; // Stores minimum // of { p, q, r, s} int Y = min(min(p, q), min(r, s)); // Update p p -= Y; // Update q q -= Y; // Update r r -= Y; // Update s s -= Y; } else if (str[i] == 'd' ) { // Update s s++; // Stores minimum // of { p, q, r, s} int Y = min(min(p, q), min(r, s)); // Update p p -= Y; // Update q q -= Y; // Update r r -= Y; // Update s s -= Y; } // Update relative frequency // of {p, q, r, s} mp[{ { p, q }, { r, s } }]++; } // Traverse the map for ( auto & e : mp) { // Stores count of // relative frequency int freq = e.second; // Update cntSub cntSub += (freq) * (freq - 1) / 2; } return cntSub; } // Driver Code int main() { string str = "abcdefg" ; // Function Call cout << countSubstrings(str); return 0; } |
Java
// Java program to implement // the above approach import java.util.*; class GFG { // Function to count the substring with // equal number of a, b, c and d static int countSubstrings(String Str) { // Stores relative frequency of // the characters {'a', 'b', 'c', 'd'} var mp = new HashMap<String, Integer>(); // Initially, frequencies of // 'a', 'b', 'c' and 'd' are 0. if (mp.containsKey( "0#0#0#0" )) mp.put( "0#0#0#0" , mp.get( "0#0#0#0" ) + 1 ); else mp.put( "0#0#0#0" , 1 ); // Stores relative // frequency of 'a' var p = 0 ; // Stores relative // frequency of 'b' var q = 0 ; // Stores relative // frequency of 'c' var r = 0 ; // Stores relative // frequency of 'd' var s = 0 ; // Stores count of substring with equal // number of 'a', 'b', 'c' and 'd' var cntSub = 0 ; // Iterate over the characters // of the string for (var i = 0 ; i < Str.length(); i++) { // If current character // is 'a' if (Str.charAt(i) == 'a' ) { // Update p p += 1 ; // Stores minimum // of { p, q, r, s} var Y = Math.min(Math.min(s, r), Math.min(p, q)); // Update p p -= Y; // Update q q -= Y; // Update r r -= Y; // Update s s -= Y; } // If current character is b else if (Str.charAt(i) == 'b' ) { // Update q q += 1 ; // Stores minimum // of { p, q, r, s} var Y = Math.min(Math.min(p, q), Math.min(r, s)); // Update p p -= Y; // Update q q -= Y; // Update r r -= Y; // Update s s -= Y; } else if (Str.charAt(i) == 'c' ) { // Update r r += 1 ; // Stores minimum // of { p, q, r, s} var Y = Math.min(Math.min(p, q),Math.min(r, s)); // Update p p -= Y; // Update q q -= Y; // Update r r -= Y; // Update s s -= Y; } else if (Str.charAt(i) == 'd' ) { // Update s s += 1 ; // Stores minimum // of { p, q, r, s} var Y = Math.min(Math.min(p, q),Math.min(r, s)); // Update p p -= Y; // Update q q -= Y; // Update r r -= Y; // Update s s -= Y; } // Update relative frequency // of {p, q, r, s} String key = String.valueOf(p) + "#" + String.valueOf(q) + "#" + String.valueOf(r) + "#" + String.valueOf(s); if (mp.containsKey(key)) mp.put(key, mp.get(key) + 1 ); else mp.put(key, 1 ); } // Traverse the map for (var e : mp.entrySet()) { // Stores count of // relative frequency var freq = e.getValue(); // Update cntSub cntSub += Math.floor((freq) * (freq - 1 ) / 2 ); } return cntSub; } // Driver code public static void main(String[] args) { var Str = "abcdefg" ; // Function Call System.out.println(countSubstrings(Str)); } } // This code is contributed by phasing17 |
Python3
# Python3 program to implement # the above approach # Function to count the substring with # equal number of a, b, c and d def countSubstrings( Str ) : # Stores relative frequency of # the characters {'a', 'b', 'c', 'd'} mp = {} # Initially, frequencies of # 'a', 'b', 'c' and 'd' are 0. if (( 0 , 0 ), ( 0 , 0 )) in mp : mp[( 0 , 0 ), ( 0 , 0 )] + = 1 else : mp[( 0 , 0 ), ( 0 , 0 )] = 1 # Stores relative # frequency of 'a' p = 0 # Stores relative # frequency of 'b' q = 0 # Stores relative # frequency of 'c' r = 0 # Stores relative # frequency of 'd' s = 0 # Stores count of substring with equal # number of 'a', 'b', 'c' and 'd' cntSub = 0 # Iterate over the characters # of the string for i in range ( len ( Str )) : # If current character # is 'a' if ( Str [i] = = 'a' ) : # Update p p + = 1 # Stores minimum # of { p, q, r, s} Y = min ( min (s, r), min (p, q)) # Update p p - = Y # Update q q - = Y # Update r r - = Y # Update s s - = Y # If current character is b elif ( Str [i] = = 'b' ) : # Update q q + = 1 # Stores minimum # of { p, q, r, s} Y = min ( min (p, q), min (r, s)) # Update p p - = Y # Update q q - = Y # Update r r - = Y # Update s s - = Y elif ( Str [i] = = 'c' ) : # Update r r + = 1 # Stores minimum # of { p, q, r, s} Y = min ( min (p, q), min (r, s)) # Update p p - = Y # Update q q - = Y # Update r r - = Y # Update s s - = Y elif ( Str [i] = = 'd' ) : # Update s s + = 1 # Stores minimum # of { p, q, r, s} Y = min ( min (p, q), min (r, s)) # Update p p - = Y # Update q q - = Y # Update r r - = Y # Update s s - = Y # Update relative frequency # of {p, q, r, s} if ((p, q), (r, s)) in mp : mp[(p, q), (r, s)] + = 1 else : mp[(p, q), (r, s)] = 1 # Traverse the map for e in mp : # Stores count of # relative frequency freq = mp[e] # Update cntSub cntSub + = (freq) * (freq - 1 ) / / 2 return cntSub # Driver code Str = "abcdefg" # Function Call print (countSubstrings( Str )) # This code is contributed by divyeshrabadiya07 |
C#
// C# program to implement // the above approach using System; using System.Collections.Generic; class GFG { // Function to count the substring with // equal number of a, b, c and d static int countSubstrings( string str) { // Stores relative frequency of // the characters {'a', 'b', 'c', 'd'} Dictionary<Tuple<Tuple< int , int >, Tuple< int , int >>, int > mp = new Dictionary<Tuple<Tuple< int , int >, Tuple< int , int >>, int >(); // Initially, frequencies of // 'a', 'b', 'c' and 'd' are 0. if (mp.ContainsKey( new Tuple<Tuple< int , int >, Tuple< int , int >>( new Tuple< int , int >(0, 0), new Tuple< int , int >(0, 0)))) { mp[ new Tuple<Tuple< int , int >, Tuple< int , int >>( new Tuple< int , int >(0, 0), new Tuple< int , int >(0, 0))]++; } else { mp[ new Tuple<Tuple< int , int >, Tuple< int , int >>( new Tuple< int , int >(0, 0), new Tuple< int , int >(0, 0))] = 1; } // Stores relative // frequency of 'a' int p = 0; // Stores relative // frequency of 'b' int q = 0; // Stores relative // frequency of 'c' int r = 0; // Stores relative // frequency of 'd' int s = 0; // Stores count of substring with equal // number of 'a', 'b', 'c' and 'd' int cntSub = 0; // Iterate over the characters // of the string for ( int i = 0; i < str.Length; i++) { // If current character // is 'a' if (str[i] == 'a' ) { // Update p p++; // Stores minimum // of { p, q, r, s} int Y = Math.Min(Math.Min(s, r), Math.Min(p, q)); // Update p p -= Y; // Update q q -= Y; // Update r r -= Y; // Update s s -= Y; } // If current character is b else if (str[i] == 'b' ) { // Update q q++; // Stores minimum // of { p, q, r, s} int Y = Math.Min(Math.Min(p, q), Math.Min(r, s)); // Update p p -= Y; // Update q q -= Y; // Update r r -= Y; // Update s s -= Y; } else if (str[i] == 'c' ) { // Update r r++; // Stores minimum // of { p, q, r, s} int Y = Math.Min(Math.Min(p, q), Math.Min(r, s)); // Update p p -= Y; // Update q q -= Y; // Update r r -= Y; // Update s s -= Y; } else if (str[i] == 'd' ) { // Update s s++; // Stores minimum // of { p, q, r, s} int Y = Math.Min(Math.Min(p, q), Math.Min(r, s)); // Update p p -= Y; // Update q q -= Y; // Update r r -= Y; // Update s s -= Y; } // Update relative frequency // of {p, q, r, s} if (mp.ContainsKey( new Tuple<Tuple< int , int >, Tuple< int , int >>( new Tuple< int , int >(p, q), new Tuple< int , int >(r, s)))) { mp[ new Tuple<Tuple< int , int >, Tuple< int , int >>( new Tuple< int , int >(p, q), new Tuple< int , int >(r, s))]++; } else { mp[ new Tuple<Tuple< int , int >, Tuple< int , int >>( new Tuple< int , int >(p, q), new Tuple< int , int >(r, s))] = 1; } } // Traverse the map foreach (KeyValuePair<Tuple<Tuple< int , int >, Tuple< int , int >>, int > e in mp) { // Stores count of // relative frequency int freq = e.Value; // Update cntSub cntSub += (freq) * (freq - 1) / 2; } return cntSub; } // Driver code static void Main() { string str = "abcdefg" ; // Function Call Console.WriteLine(countSubstrings(str)); } } // This code is contributed by divyesh072019 |
Javascript
// JS program to implement // the above approach // Function to count the substring with // equal number of a, b, c and d function countSubstrings(Str) { // Stores relative frequency of // the characters {'a', 'b', 'c', 'd'} let mp = {} // Initially, frequencies of // 'a', 'b', 'c' and 'd' are 0. if (mp.hasOwnProperty( '0#0#0#0' )) mp[ '0#0#0#0' ] += 1 else mp[ '0#0#0#0' ] = 1 // Stores relative // frequency of 'a' let p = 0 // Stores relative // frequency of 'b' let q = 0 // Stores relative // frequency of 'c' let r = 0 // Stores relative // frequency of 'd' let s = 0 // Stores count of substring with equal // number of 'a', 'b', 'c' and 'd' let cntSub = 0 // Iterate over the characters // of the string for ( var i = 0; i < Str.length; i++) { // If current character // is 'a' if (Str.charAt(i) == 'a' ) { // Update p p += 1 // Stores minimum // of { p, q, r, s} let Y = Math.min(Math.min(s, r), Math.min(p, q)) // Update p p -= Y // Update q q -= Y // Update r r -= Y // Update s s -= Y } // If current character is b else if (Str[i] == 'b' ) { // Update q q += 1 // Stores minimum // of { p, q, r, s} let Y = Math.min(Math.min(p, q), Math.min(r, s)) // Update p p -= Y // Update q q -= Y // Update r r -= Y // Update s s -= Y } else if (Str[i] == 'c' ) { // Update r r += 1 // Stores minimum // of { p, q, r, s} let Y = Math.min(Math.min(p, q),Math.min(r, s)) // Update p p -= Y // Update q q -= Y // Update r r -= Y // Update s s -= Y } else if (Str[i] == 'd' ) { // Update s s += 1 // Stores minimum // of { p, q, r, s} Y = Math.min(Math.min(p, q),Math.min(r, s)) // Update p p -= Y // Update q q -= Y // Update r r -= Y // Update s s -= Y } // Update relative frequency // of {p, q, r, s} let key = `${p} #${q}#${r}#${s}` if (mp.hasOwnProperty(key)) mp[key] += 1 else mp[key] = 1 } // Traverse the map for (let e of Object.keys(mp)) { // Stores count of // relative frequency freq = mp[e] // Update cntSub cntSub += Math.floor((freq) * (freq - 1) / 2) } return cntSub } // Driver code let Str = "abcdefg" // Function Call console.log(countSubstrings(Str)) // This code is contributed by phasing17 |
Output:
10
Time Complexity: O(N * Log(N))
Auxiliary Space: O(N)