Count number of rotated strings which have more number of vowels in the first half than second half | C ++ implementation of the approach ; Function to return the count of rotated strings which have more number of vowels in the first half than the second half ; Create a new string ; Pre array to store count of all vowels ; Compute the prefix array ; To store the required answer ; Find all rotated strings ; Right and left index of the string ; x1 stores the number of vowels in the rotated string ; Left stores the number of vowels in the first half of rotated string ; Right stores the number of vowels in the second half of rotated string ; If the count of vowels in the first half is greater than the count in the second half ; Return the required answer ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int cntRotations ( string s , int n ) { string str = s + s ; int pre [ 2 * n ] = { 0 } ; for ( int i = 0 ; i < 2 * n ; i ++ ) { if ( i != 0 ) pre [ i ] += pre [ i - 1 ] ; if ( str [ i ] == ' a ' str [ i ] == ' e ' str [ i ] == ' i ' str [ i ] == ' o ' str [ i ] == ' u ' ) { pre [ i ] ++ ; } } int ans = 0 ; for ( int i = n - 1 ; i < 2 * n - 1 ; i ++ ) { int r = i , l = i - n ; int x1 = pre [ r ] ; if ( l >= 0 ) x1 -= pre [ l ] ; r = i - n / 2 ; int left = pre [ r ] ; if ( l >= 0 ) left -= pre [ l ] ; int right = x1 - left ; if ( left > right ) { ans ++ ; } } return ans ; } int main ( ) { string s = " abecidft " ; int n = s . length ( ) ; cout << cntRotations ( s , n ) ; return 0 ; }