Lexicographically largest string possible in one swap | Function to return the lexicographically largest string possible by swapping at most one character ; Initialize with - 1 for every character ; Keep updating the last occurrence of each character ; If a previously unvisited character occurs ; Stores the sorted string ; Character to replace ; Find the last occurrence of this character ; Swap this with the last occurrence ; Driver code
def findLargest ( s ) : NEW_LINE INDENT Len = len ( s ) NEW_LINE loccur = [ - 1 for i in range ( 26 ) ] NEW_LINE for i in range ( Len - 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 = sorted ( s , reverse = True ) NEW_LINE for i in range ( Len ) : 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 temp = list ( s ) NEW_LINE temp [ i ] , temp [ last_occ ] = ( temp [ last_occ ] , temp [ i ] ) NEW_LINE s = " " . join ( temp ) NEW_LINE break NEW_LINE DEDENT DEDENT return s NEW_LINE DEDENT s = " yrstvw " NEW_LINE print ( findLargest ( s ) ) NEW_LINE