Longest substring consisting of vowels using Binary Search | Function to check if a character is vowel or not ; 0 - a 1 - b 2 - c and so on 25 - z ; Function to check if any substring of length k exists which contains only vowels ; Applying sliding window to get all substrings of length K ; Remove the occurence of ( i - k + 1 ) th character ; Function to perform Binary Search ; Doing binary search on the lengths ; Driver Code
def vowel ( vo ) : NEW_LINE INDENT if ( vo == 0 or vo == 4 or vo == 8 or vo == 14 or vo == 20 ) : NEW_LINE INDENT return True NEW_LINE DEDENT else : NEW_LINE INDENT return False NEW_LINE DEDENT DEDENT def check ( s , k ) : NEW_LINE INDENT cnt = [ 0 ] * 26 NEW_LINE for i in range ( k - 1 ) : NEW_LINE INDENT cnt [ ord ( s [ i ] ) - ord ( ' a ' ) ] += 1 NEW_LINE DEDENT for i in range ( k - 1 , len ( s ) ) : NEW_LINE INDENT cnt [ ord ( s [ i ] ) - ord ( ' a ' ) ] += 1 NEW_LINE flag1 = 0 NEW_LINE for j in range ( 26 ) : NEW_LINE INDENT if ( vowel ( j ) == False and cnt [ j ] > 0 ) : NEW_LINE INDENT flag1 = 1 NEW_LINE break NEW_LINE DEDENT DEDENT if ( flag1 == 0 ) : NEW_LINE INDENT return True NEW_LINE DEDENT cnt [ ord ( s [ i - k + 1 ] ) - ord ( ' a ' ) ] -= 1 NEW_LINE DEDENT return False NEW_LINE DEDENT def longestSubstring ( s ) : NEW_LINE INDENT l = 1 NEW_LINE r = len ( s ) NEW_LINE maxi = 0 NEW_LINE while ( l <= r ) : NEW_LINE INDENT mid = ( l + r ) // 2 NEW_LINE if ( check ( s , mid ) ) : NEW_LINE INDENT l = mid + 1 NEW_LINE maxi = max ( maxi , mid ) NEW_LINE DEDENT else : NEW_LINE INDENT r = mid - 1 NEW_LINE DEDENT DEDENT return maxi NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT s = " sedrewaefhoiu " NEW_LINE print ( longestSubstring ( s ) ) NEW_LINE DEDENT