Prefixes with more a than b | CPP code to count the prefixes with more a than b ; Function to count prefixes ; calculating for string S ; count == 0 or when N == 1 ; when all characters are a or a - b == 0 ; checking for saturation of string after repetitive addition ; Driver function
#include <bits/stdc++.h> NEW_LINE using namespace std ; int prefix ( string k , int n ) { int a = 0 , b = 0 , count = 0 ; int i = 0 ; int len = k . size ( ) ; for ( i = 0 ; i < len ; i ++ ) { if ( k [ i ] == ' a ' ) a ++ ; if ( k [ i ] == ' b ' ) b ++ ; if ( a > b ) { count ++ ; } } if ( count == 0 n == 1 ) { cout << count << endl ; return 0 ; } if ( count == len a - b == 0 ) { cout << count * n << endl ; return 0 ; } int n2 = n - 1 , count2 = 0 ; while ( n2 != 0 ) { for ( i = 0 ; i < len ; i ++ ) { if ( k [ i ] == ' a ' ) a ++ ; if ( k [ i ] == ' b ' ) b ++ ; if ( a > b ) { count2 ++ ; } } count += count2 ; n2 -- ; if ( count2 == 0 ) break ; if ( count2 == len ) { count += ( n2 * count2 ) ; break ; } count2 = 0 ; } return count ; } int main ( ) { string S = " aba " ; int N = 2 ; cout << prefix ( S , N ) << endl ; S = " baa " ; N = 3 ; cout << prefix ( S , N ) << endl ; return 0 ; }