Sub | Function that returns true if every lowercase character appears atmost once ; Every character frequency must be not greater than one ; Function that returns the modified good string if possible ; If the length of the string is less than n ; Sub - strings of length 26 ; To store frequency of each character ; Get the frequency of each character in the current sub - string ; Check if we can get sub - string containing the 26 characters all ; Find which character is missing ; Fill with missing characters ; Find the next missing character ; Return the modified good string ; Driver code
def valid ( cnt ) : NEW_LINE INDENT for i in range ( 0 , 26 ) : NEW_LINE INDENT if cnt [ i ] >= 2 : NEW_LINE INDENT return False NEW_LINE DEDENT DEDENT return True NEW_LINE DEDENT def getGoodString ( s , n ) : NEW_LINE INDENT if n < 26 : NEW_LINE INDENT return " - 1" NEW_LINE DEDENT for i in range ( 25 , n ) : NEW_LINE INDENT cnt = [ 0 ] * 26 NEW_LINE for j in range ( i , i - 26 , - 1 ) : NEW_LINE INDENT if s [ j ] != ' ? ' : NEW_LINE INDENT cnt [ ord ( s [ j ] ) - ord ( ' a ' ) ] += 1 NEW_LINE DEDENT DEDENT if valid ( cnt ) : NEW_LINE INDENT cur = 0 NEW_LINE while cur < 26 and cnt [ cur ] > 0 : NEW_LINE INDENT cur += 1 NEW_LINE DEDENT for j in range ( i - 25 , i + 1 ) : NEW_LINE INDENT if s [ j ] == ' ? ' : NEW_LINE INDENT s [ j ] = chr ( cur + ord ( ' a ' ) ) NEW_LINE cur += 1 NEW_LINE while cur < 26 and cnt [ cur ] > 0 : NEW_LINE INDENT cur += 1 NEW_LINE DEDENT DEDENT DEDENT return ' ' . join ( s ) NEW_LINE DEDENT DEDENT return " - 1" NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT s = " abcdefghijkl ? nopqrstuvwxy ? " NEW_LINE n = len ( s ) NEW_LINE print ( getGoodString ( list ( s ) , n ) ) NEW_LINE DEDENT