Find the longest substring with k unique characters in a given string | Python program to find the longest substring with k unique characters in a given string ; This function calculates number of unique characters using a associative array count [ ] . Returns true if no . of characters are less than required else returns false . ; Return true if k is greater than or equal to val ; Finds the maximum substring with exactly k unique characters ; Associative array to store the count ; Tranverse the string , fills the associative array count [ ] and count number of unique characters ; If there are not enough unique characters , show an error message . ; Otherwise take a window with first element in it . start and end variables . ; Also initialize values for result longest window ; Initialize associative array count [ ] with zero ; put the first character ; Start from the second character and add characters in window according to above explanation ; Add the character ' s [ i ] ' to current window ; If there are more than k unique characters in current window , remove from left side ; Update the max window size if required ; Driver function
MAX_CHARS = 26 NEW_LINE def isValid ( count , k ) : NEW_LINE INDENT val = 0 NEW_LINE for i in range ( MAX_CHARS ) : NEW_LINE INDENT if count [ i ] > 0 : NEW_LINE INDENT val += 1 NEW_LINE DEDENT DEDENT return ( k >= val ) NEW_LINE DEDENT def kUniques ( s , k ) : NEW_LINE INDENT count = [ 0 ] * MAX_CHARS NEW_LINE for i in range ( n ) : NEW_LINE INDENT if count [ ord ( s [ i ] ) - ord ( ' a ' ) ] == 0 : NEW_LINE INDENT u += 1 NEW_LINE DEDENT count [ ord ( s [ i ] ) - ord ( ' a ' ) ] += 1 NEW_LINE DEDENT if u < k : NEW_LINE INDENT print ( " Not ▁ enough ▁ unique ▁ characters " ) NEW_LINE return NEW_LINE DEDENT curr_start = 0 NEW_LINE curr_end = 0 NEW_LINE max_window_size = 1 NEW_LINE max_window_start = 0 NEW_LINE count = [ 0 ] * len ( count ) NEW_LINE count [ ord ( s [ 0 ] ) - ord ( ' a ' ) ] += 1 NEW_LINE for i in range ( 1 , n ) : NEW_LINE INDENT count [ ord ( s [ i ] ) - ord ( ' a ' ) ] += 1 NEW_LINE curr_end += 1 NEW_LINE while not isValid ( count , k ) : NEW_LINE INDENT count [ ord ( s [ curr_start ] ) - ord ( ' a ' ) ] -= 1 NEW_LINE curr_start += 1 NEW_LINE DEDENT if curr_end - curr_start + 1 > max_window_size : NEW_LINE INDENT max_window_size = curr_end - curr_start + 1 NEW_LINE max_window_start = curr_start NEW_LINE DEDENT DEDENT print ( " Max ▁ substring ▁ is ▁ : ▁ " + s [ max_window_start : max_window_start + max_window_size ] + " ▁ with ▁ length ▁ " + str ( max_window_size ) ) NEW_LINE DEDENT s = " aabacbebebe " NEW_LINE k = 3 NEW_LINE kUniques ( s , k ) NEW_LINE