Find lexicographically smallest string in at most one swaps | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; string findSmallest ( string s ) { int len = s . size ( ) ; int loccur [ 26 ] ; memset ( loccur , -1 , sizeof ( loccur ) ) ; for ( int i = len - 1 ; i >= 0 ; -- i ) { int chI = s [ i ] - ' a ' ; if ( loccur [ chI ] == -1 ) { loccur [ chI ] = i ; } } string sorted_s = s ; sort ( sorted_s . begin ( ) , sorted_s . end ( ) ) ; for ( int i = 0 ; i < len ; ++ i ) { if ( s [ i ] != sorted_s [ i ] ) { int chI = sorted_s [ i ] - ' a ' ; int last_occ = loccur [ chI ] ; swap ( s [ i ] , s [ last_occ ] ) ; break ; } } return s ; } int main ( ) { string s = " geeks " ; cout << findSmallest ( s ) ; return 0 ; }