Count substrings consisting of equal number of a , b , c and d | C ++ program to implement the above approach ; Function to count the substring with equal number of a , b , c and d ; Stores relative frequency of the characters { ' a ' , ' b ' , ' c ' , ' d ' } ; Initially , frequencies of ' a ' , ' b ' , ' c ' and ' d ' are 0. ; Stores relative frequency of ' a ' ; Stores relative frequency of ' b ' ; Stores relative frequency of ' c ' ; Stores relative frequency of ' d ' ; Stores count of substring with equal number of ' a ' , ' b ' , ' c ' and ' d ' ; Iterate over the characters of the string ; If current character is ' a ' ; Update p ; Stores minimum of { p , q , r , s } ; Update p ; Update q ; Update r ; Update s ; If current character is b ; Update q ; Stores minimum of { p , q , r , s } ; Update p ; Update q ; Update r ; Update s ; Update r ; Stores minimum of { p , q , r , s } ; Update p ; Update q ; Update r ; Update s ; Update s ; Stores minimum of { p , q , r , s } ; Update p ; Update q ; Update r ; Update s ; Update relative frequency of { p , q , r , s } ; Traverse the map ; Stores count of relative frequency ; Update cntSub ; Driver Code ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; int countSubstrings ( string str ) { map < pair < pair < int , int > , pair < int , int > > , int > mp ; mp [ { { 0 , 0 } , { 0 , 0 } } ] ++ ; int p = 0 ; int q = 0 ; int r = 0 ; int s = 0 ; int cntSub = 0 ; for ( int i = 0 ; i < str . length ( ) ; i ++ ) { if ( str [ i ] == ' a ' ) { p ++ ; int Y = min ( min ( s , r ) , min ( p , q ) ) ; p -= Y ; q -= Y ; r -= Y ; s -= Y ; } else if ( str [ i ] == ' b ' ) { q ++ ; int Y = min ( min ( p , q ) , min ( r , s ) ) ; p -= Y ; q -= Y ; r -= Y ; s -= Y ; } else if ( str [ i ] == ' c ' ) { r ++ ; int Y = min ( min ( p , q ) , min ( r , s ) ) ; p -= Y ; q -= Y ; r -= Y ; s -= Y ; } else if ( str [ i ] == ' d ' ) { s ++ ; int Y = min ( min ( p , q ) , min ( r , s ) ) ; p -= Y ; q -= Y ; r -= Y ; s -= Y ; } mp [ { { p , q } , { r , s } } ] ++ ; } for ( auto & e : mp ) { int freq = e . second ; cntSub += ( freq ) * ( freq - 1 ) / 2 ; } return cntSub ; } int main ( ) { string str = " abcdefg " ; cout << countSubstrings ( str ) ; return 0 ; }