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 . ; Store last occurrence of every character ; 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 ; Driver code
function findSmallest ( s ) { let len = s . length ; let loccur = new Array ( 26 ) ; loccur . fill ( - 1 ) ; for ( let i = len - 1 ; i >= 0 ; -- i ) { let chI = s [ i ] . charCodeAt ( ) - ' ' . charCodeAt ( ) ; if ( loccur [ chI ] == - 1 ) { loccur [ chI ] = i ; } } let sorted_s = s ; sorted_s . sort ( ) ; for ( let i = 0 ; i < len ; ++ i ) { if ( s [ i ] != sorted_s [ i ] ) { let chI = sorted_s [ i ] . charCodeAt ( ) - ' ' . charCodeAt ( ) ; let last_occ = loccur [ chI ] ; let temp = s [ i ] ; s [ i ] = s [ last_occ ] ; s [ last_occ ] = temp ; break ; } } return s . join ( " " ) ; } let s = " " ; document . write ( findSmallest ( s . split ( ' ' ) ) ) ;