Minimize length of Substrings containing at least one common Character | Function to check and return if substrings of length mid has a common character a ; Length of the string ; Initialise the first occurrence of character a ; Check that distance b / w the current and previous occurrence of character a is less than or equal to mid ; If distance exceeds mid ; Function to check for all the alphabets , if substrings of length mid have a character common ; Check for all 26 alphabets ; Check that char i + a is common in all the substrings of length mid ; If no characters is common ; Function to calculate and return the minm length of substrings ; Initialise low and high ; Perform binary search ; Update mid ; Check if one common character is present in the length of the mid ; Returns the minimum length that contain one common character ; Function to check if all characters are distinct ; Driver Code
def check ( st , mid , a ) : NEW_LINE INDENT n = len ( st ) NEW_LINE previous = - 1 NEW_LINE for i in range ( n ) : NEW_LINE INDENT if ( st [ i ] == chr ( a ) ) : NEW_LINE INDENT if ( i - previous > mid ) : NEW_LINE INDENT return False NEW_LINE DEDENT previous = i NEW_LINE DEDENT DEDENT if ( i - previous > mid ) : NEW_LINE INDENT return False NEW_LINE DEDENT else : NEW_LINE INDENT return True NEW_LINE DEDENT DEDENT def possible ( st , mid ) : NEW_LINE INDENT for i in range ( 26 ) : NEW_LINE INDENT if ( check ( st , mid , i + ord ( ' a ' ) ) ) : NEW_LINE INDENT return True NEW_LINE DEDENT DEDENT return False NEW_LINE DEDENT def findMinLength ( st ) : NEW_LINE INDENT low = 1 NEW_LINE high = len ( st ) NEW_LINE while ( low <= high ) : NEW_LINE INDENT mid = ( low + high ) // 2 NEW_LINE if ( possible ( st , mid ) ) : NEW_LINE INDENT high = mid - 1 NEW_LINE DEDENT else : NEW_LINE INDENT low = mid + 1 NEW_LINE DEDENT DEDENT return high + 1 NEW_LINE DEDENT def ifAllDistinct ( st ) : NEW_LINE INDENT s = [ ] NEW_LINE for c in st : NEW_LINE INDENT s . append ( c ) NEW_LINE DEDENT return len ( set ( s ) ) == len ( st ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT st = " geeksforgeeks " NEW_LINE if ( ifAllDistinct ( st ) ) : NEW_LINE INDENT print ( " - 1" ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( findMinLength ( st ) ) NEW_LINE DEDENT DEDENT