Find lexicographically smallest string in at most one swaps | Java implementation of the above approach ; 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
import java . util . * ; class GFG { static String findSmallest ( char [ ] s ) { int len = s . length ; int [ ] loccur = new int [ 26 ] ; Arrays . fill ( loccur , - 1 ) ; for ( int i = len - 1 ; i >= 0 ; -- i ) { int chI = s [ i ] - ' a ' ; if ( loccur [ chI ] == - 1 ) { loccur [ chI ] = i ; } } char [ ] sorted_s = s ; Arrays . sort ( sorted_s ) ; for ( int i = 0 ; i < len ; ++ i ) { if ( s [ i ] != sorted_s [ i ] ) { int chI = sorted_s [ i ] - ' a ' ; int last_occ = loccur [ chI ] ; char temp = s [ last_occ ] ; s [ last_occ ] = s [ i ] ; s [ i ] = temp ; break ; } } return String . valueOf ( s ) ; } public static void main ( String [ ] args ) { String s = " geeks " ; System . out . print ( findSmallest ( s . toCharArray ( ) ) ) ; } }