Length of the smallest substring which contains all vowels | C ++ Program to find the length of the smallest substring of which contains all vowels ; Map to store the frequency of vowels ; Store the indices which contains the vowels ; If all vowels are not present in the string ; If the frequency of the vowel at i - th index exceeds 1 ; Decrease the frequency of that vowel ; Move to the left ; Otherwise set flag1 ; If the frequency of the vowel at j - th index exceeds 1 ; Decrease the frequency of that vowel ; Move to the right ; Otherwise set flag2 ; If both flag1 and flag2 are set , break out of the loop as the substring length cannot be minimized ; Return the length of the substring ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int findMinLength ( string s ) { int n = s . size ( ) ; map < char , int > counts ; vector < int > indices ; for ( int i = 0 ; i < n ; i ++ ) { if ( s [ i ] == ' a ' s [ i ] == ' e ' s [ i ] == ' o ' s [ i ] == ' i ' s [ i ] == ' u ' ) { counts [ s [ i ] ] ++ ; indices . push_back ( i ) ; } } if ( counts . size ( ) < 5 ) return -1 ; int flag1 = 0 , flag2 = 0 ; int i = 0 ; int j = indices . size ( ) - 1 ; while ( ( j - i ) >= 4 ) { if ( ! flag1 && counts [ s [ indices [ i ] ] ] > 1 ) { counts [ s [ indices [ i ] ] ] -- ; i ++ ; } else flag1 = 1 ; if ( ! flag2 && counts [ s [ indices [ j ] ] ] > 1 ) { counts [ s [ indices [ j ] ] ] -- ; j -- ; } else flag2 = 1 ; if ( flag1 && flag2 ) break ; } return ( indices [ j ] - indices [ i ] + 1 ) ; } int main ( ) { string s = " aaeebbeaccaaoiuooooooooiuu " ; cout << findMinLength ( s ) ; return 0 ; }