Swap all occurrences of two characters to get lexicographically smallest string | C ++ implementation of the approach ; Function to return the lexicographically smallest string after swapping all the occurrences of any two characters ; To store the first index of every character of str ; Store the first occurring index every character ; If current character is appearing for the first time in str ; Starting from the leftmost character ; For every character smaller than str [ i ] ; If there is a character in str which is smaller than str [ i ] and appears after it ; If the required character pair is found ; If swapping is possible ; Characters to be swapped ; For every character ; Replace every ch1 with ch2 and every ch2 with ch1 ; Driver code
#include <iostream> NEW_LINE using namespace std ; #define MAX  26 NEW_LINE string smallestStr ( string str , int n ) { int i , j ; int chk [ MAX ] ; for ( i = 0 ; i < MAX ; i ++ ) chk [ i ] = -1 ; for ( i = 0 ; i < n ; i ++ ) { if ( chk [ str [ i ] - ' a ' ] == -1 ) chk [ str [ i ] - ' a ' ] = i ; } for ( i = 0 ; i < n ; i ++ ) { bool flag = false ; for ( j = 0 ; j < str [ i ] - ' a ' ; j ++ ) { if ( chk [ j ] > chk [ str [ i ] - ' a ' ] ) { flag = true ; break ; } } if ( flag ) break ; } if ( i < n ) { char ch1 = str [ i ] ; char ch2 = char ( j + ' a ' ) ; for ( i = 0 ; i < n ; i ++ ) { if ( str [ i ] == ch1 ) str [ i ] = ch2 ; else if ( str [ i ] == ch2 ) str [ i ] = ch1 ; } } return str ; } int main ( ) { string str = " ccad " ; int n = str . length ( ) ; cout << smallestStr ( str , n ) ; return 0 ; }