Minimum changes to a string to make all substrings distinct | Python3 program to count number of changes to make all substrings distinct . ; Returns minimum changes to str so that no substring is repeated . ; If length is more than maximum allowed characters , we cannot get the required string . ; Variable to store count of distinct characters ; To store counts of different characters ; Answer is , n - number of distinct char ; Driver Code
MAX_CHAR = [ 26 ] NEW_LINE def minChanges ( str ) : NEW_LINE INDENT n = len ( str ) NEW_LINE if ( n > MAX_CHAR [ 0 ] ) : NEW_LINE INDENT return - 1 NEW_LINE DEDENT dist_count = 0 NEW_LINE count = [ 0 ] * MAX_CHAR [ 0 ] NEW_LINE for i in range ( n ) : NEW_LINE INDENT if ( count [ ord ( str [ i ] ) - ord ( ' a ' ) ] == 0 ) : NEW_LINE INDENT dist_count += 1 NEW_LINE DEDENT count [ ( ord ( str [ i ] ) - ord ( ' a ' ) ) ] += 1 NEW_LINE DEDENT return ( n - dist_count ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT str = " aebaecedabbee " NEW_LINE print ( minChanges ( str ) ) NEW_LINE DEDENT