text: Lexicographically smallest K | C ++ program to find lexicographically smallest K - length substring containing maximum number of vowels ; Function that prints the lexicographically smallest K - length substring containing maximum number of vowels ; Store the length of the string ; Initialize a prefix sum array ; Loop through the string to create the prefix sum array ; Store 1 at the index if it is a vowel ; Otherwise , store 0 ; Process the prefix array ; Initialize the variable to store maximum count of vowels ; Initialize the variable to store substring with maximum count of vowels ; Loop through the prefix array ; Store the current count of vowels ; Update the result if current count is greater than maximum count ; Update lexicographically smallest substring if the current count is equal to the maximum count ; Return the result ; Driver Program
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; string maxVowelSubString ( string str , int K ) { int N = str . length ( ) ; int pref [ N ] ; for ( int i = 0 ; i < N ; i ++ ) { if ( str [ i ] == ' a ' or str [ i ] == ' e ' or str [ i ] == ' i ' or str [ i ] == ' o ' or str [ i ] == ' u ' ) pref [ i ] = 1 ; else pref [ i ] = 0 ; if ( i ) pref [ i ] += pref [ i - 1 ] ; } int maxCount = pref [ K - 1 ] ; string res = str . substr ( 0 , K ) ; for ( int i = K ; i < N ; i ++ ) { int currCount = pref [ i ] - pref [ i - K ] ; if ( currCount > maxCount ) { maxCount = currCount ; res = str . substr ( i - K + 1 , K ) ; } else if ( currCount == maxCount ) { string temp = str . substr ( i - K + 1 , K ) ; if ( temp < res ) res = temp ; } } return res ; } int main ( ) { string str = " ceebbaceeffo " ; int K = 3 ; cout << maxVowelSubString ( str , K ) ; return 0 ; }