Length of the smallest substring which contains all vowels | Python3 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
from collections import defaultdict NEW_LINE def findMinLength ( s ) : NEW_LINE INDENT n = len ( s ) NEW_LINE counts = defaultdict ( int ) NEW_LINE indices = [ ] NEW_LINE for i in range ( n ) : NEW_LINE INDENT if ( s [ i ] == ' a ' or s [ i ] == ' e ' or s [ i ] == ' o ' or s [ i ] == ' i ' or s [ i ] == ' u ' ) : NEW_LINE INDENT counts [ s [ i ] ] += 1 NEW_LINE indices . append ( i ) NEW_LINE DEDENT DEDENT if len ( counts ) < 5 : NEW_LINE INDENT return - 1 NEW_LINE DEDENT flag1 = 0 NEW_LINE flag2 = 0 NEW_LINE i = 0 NEW_LINE j = len ( indices ) - 1 NEW_LINE while ( j - i ) >= 4 : NEW_LINE INDENT if ( ~ flag1 and counts [ s [ indices [ i ] ] ] > 1 ) : NEW_LINE INDENT counts [ s [ indices [ i ] ] ] -= 1 NEW_LINE i += 1 NEW_LINE DEDENT else : NEW_LINE INDENT flag1 = 1 NEW_LINE DEDENT if ( ~ flag2 and counts [ s [ indices [ j ] ] ] > 1 ) : NEW_LINE INDENT counts [ s [ indices [ j ] ] ] -= 1 NEW_LINE j -= 1 NEW_LINE DEDENT else : NEW_LINE INDENT flag2 = 1 NEW_LINE DEDENT if ( flag1 and flag2 ) : NEW_LINE INDENT break NEW_LINE DEDENT DEDENT return ( indices [ j ] - indices [ i ] + 1 ) NEW_LINE DEDENT s = " aaeebbeaccaaoiuooooooooiuu " NEW_LINE print ( findMinLength ( s ) ) NEW_LINE