Minimum K such that every substring of length atleast K contains a character c | This function checks if there exists some character which appears in all K length substrings ; Iterate over all possible characters ; stores the last occurrence ; set answer as true ; No occurrence found of current character in first substring of length K ; Check for every last substring of length K where last occurr - ence exists in substring ; If last occ is not present in substring ; current character is K amazing ; This function performs binary search over the answer to minimise it ; Check if answer is found try to minimise it ; Driver Code
def check ( s , K ) : NEW_LINE INDENT for ch in range ( 0 , 26 ) : NEW_LINE INDENT c = chr ( 97 + ch ) NEW_LINE last = - 1 NEW_LINE found = True NEW_LINE for i in range ( 0 , K ) : NEW_LINE INDENT if s [ i ] == c : NEW_LINE INDENT last = i NEW_LINE DEDENT DEDENT if last == - 1 : NEW_LINE INDENT continue NEW_LINE DEDENT for i in range ( K , len ( s ) ) : NEW_LINE INDENT if s [ i ] == c : NEW_LINE INDENT last = i NEW_LINE DEDENT if last <= ( i - K ) : NEW_LINE INDENT found = False NEW_LINE break NEW_LINE DEDENT DEDENT if found : NEW_LINE INDENT return 1 NEW_LINE DEDENT DEDENT return 0 NEW_LINE DEDENT def binarySearch ( s ) : NEW_LINE INDENT low , high , ans = 1 , len ( s ) , None NEW_LINE while low <= high : NEW_LINE INDENT mid = ( high + low ) >> 1 NEW_LINE if check ( s , mid ) : NEW_LINE INDENT ans , high = mid , mid - 1 NEW_LINE DEDENT else : NEW_LINE INDENT low = mid + 1 NEW_LINE DEDENT DEDENT return ans NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT s = " abcde " NEW_LINE print ( binarySearch ( s ) ) NEW_LINE s = " aaaa " NEW_LINE print ( binarySearch ( s ) ) NEW_LINE DEDENT