Find lexicographically smallest string in at most one swaps | Function to return the lexicographically smallest string that can be formed by swapping at most one character . The characters might not necessarily be adjacent . ; Set - 1 as default for every character . ; Character index to fill in the last occurrence array ; If this is true then this character is being visited for the first time from the last Thus last occurrence of this character is stored in this index ; Character to replace ; Find the last occurrence of this character . ; Swap this with the last occurrence swap ( s [ i ] , s [ last_occ ] ) ; ; Driver code
def findSmallest ( s ) : NEW_LINE INDENT length = len ( s ) ; NEW_LINE loccur = [ - 1 ] * 26 ; NEW_LINE for i in range ( length - 1 , - 1 , - 1 ) : NEW_LINE INDENT chI = ord ( s [ i ] ) - ord ( ' a ' ) ; NEW_LINE if ( loccur [ chI ] == - 1 ) : NEW_LINE INDENT loccur [ chI ] = i ; NEW_LINE DEDENT DEDENT sorted_s = s ; NEW_LINE sorted_s . sort ( ) ; NEW_LINE for i in range ( length ) : NEW_LINE INDENT if ( s [ i ] != sorted_s [ i ] ) : NEW_LINE INDENT chI = ord ( sorted_s [ i ] ) - ord ( ' a ' ) ; NEW_LINE last_occ = loccur [ chI ] ; NEW_LINE s [ i ] , s [ last_occ ] = s [ last_occ ] , s [ i ] NEW_LINE break ; NEW_LINE DEDENT DEDENT return " " . join ( s ) ; NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT s = " geeks " ; NEW_LINE print ( findSmallest ( list ( s ) ) ) ; NEW_LINE DEDENT