Longest substring where all the characters appear at least K times | Set 3 | Function to find the length of the longest substring ; Store the required answer ; Create a frequency map of the characters of the string ; Store the length of the string ; Traverse the string , s ; Increment the frequency of the current character by 1 ; Stores count of unique characters ; Find the number of unique characters in string ; Iterate in range [ 1 , unique ] ; Initialize frequency of all characters as 0 ; Stores the start and the end of the window ; Stores the current number of unique characters and characters occuring atleast K times ; New unique character ; New character which occurs atleast k times ; Expand window by incrementing end by 1 ; Check if this character is present atleast k times ; Check if this character is unique ; Shrink the window by incrementing start by 1 ; If there are curr_unique characters and each character is atleast k times ; Update the overall maximum length ; Print the answer ;
def longestSubstring ( s , k ) : NEW_LINE INDENT ans = 0 NEW_LINE freq = [ 0 ] * 26 NEW_LINE n = len ( s ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT freq [ ord ( s [ i ] ) - ord ( ' a ' ) ] += 1 NEW_LINE DEDENT unique = 0 NEW_LINE for i in range ( 26 ) : NEW_LINE INDENT if ( freq [ i ] != 0 ) : NEW_LINE INDENT unique += 1 NEW_LINE DEDENT DEDENT for curr_unique in range ( 1 , unique + 1 ) : NEW_LINE INDENT Freq = [ 0 ] * 26 NEW_LINE start , end = 0 , 0 NEW_LINE cnt , count_k = 0 , 0 NEW_LINE while ( end < n ) : NEW_LINE INDENT if ( cnt <= curr_unique ) : NEW_LINE INDENT ind = ord ( s [ end ] ) - ord ( ' a ' ) NEW_LINE if ( Freq [ ind ] == 0 ) : NEW_LINE INDENT cnt += 1 NEW_LINE DEDENT Freq [ ind ] += 1 NEW_LINE if ( Freq [ ind ] == k ) : NEW_LINE INDENT count_k += 1 NEW_LINE DEDENT end += 1 NEW_LINE DEDENT else : NEW_LINE INDENT ind = ord ( s [ start ] ) - ord ( ' a ' ) NEW_LINE if ( Freq [ ind ] == k ) : NEW_LINE INDENT count_k -= 1 NEW_LINE DEDENT Freq [ ind ] -= 1 NEW_LINE if ( Freq [ ind ] == 0 ) : NEW_LINE INDENT cnt -= 1 NEW_LINE DEDENT start += 1 NEW_LINE DEDENT if ( ( cnt == curr_unique ) and ( count_k == curr_unique ) ) : NEW_LINE INDENT ans = max ( ans , end - start ) NEW_LINE DEDENT DEDENT DEDENT print ( ans ) NEW_LINE DEDENT / * Driver Code * / NEW_LINE S = " aabbba " NEW_LINE K = 3 NEW_LINE longestSubstring ( S , K ) NEW_LINE