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
using System ; using System . Collections . Generic ; class GFG { static int countSubstrings ( string str ) { Dictionary < Tuple < Tuple < int , int > , Tuple < int , int > > , int > mp = new Dictionary < Tuple < Tuple < int , int > , Tuple < int , int > > , int > ( ) ; 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 ; } 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 = Math . Min ( Math . Min ( s , r ) , Math . Min ( p , q ) ) ; p -= Y ; q -= Y ; r -= Y ; s -= Y ; } else if ( str [ i ] == ' b ' ) { q ++ ; int Y = Math . Min ( Math . Min ( p , q ) , Math . Min ( r , s ) ) ; p -= Y ; q -= Y ; r -= Y ; s -= Y ; } else if ( str [ i ] == ' c ' ) { r ++ ; int Y = Math . Min ( Math . Min ( p , q ) , Math . Min ( r , s ) ) ; p -= Y ; q -= Y ; r -= Y ; s -= Y ; } else if ( str [ i ] == ' d ' ) { s ++ ; int Y = Math . Min ( Math . Min ( p , q ) , Math . Min ( r , s ) ) ; p -= Y ; q -= Y ; r -= Y ; s -= Y ; } 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 ; } } foreach ( KeyValuePair < Tuple < Tuple < int , int > , Tuple < int , int > > , int > e in mp ) { int freq = e . Value ; cntSub += ( freq ) * ( freq - 1 ) / 2 ; } return cntSub ; } static void Main ( ) { string str = " abcdefg " ; Console . WriteLine ( countSubstrings ( str ) ) ; } }