Lexicographically largest string possible in one swap | C ++ implementation to find the lexicographically largest string by atmost at most one swap ; Function to return the lexicographically largest string possible by swapping at most one character ; Stores last occurrence of every 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 Program
#include <bits/stdc++.h> NEW_LINE using namespace std ; string findLargest ( 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 ( ) , greater < int > ( ) ) ; 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 = " yrstvw " ; cout << findLargest ( s ) ; return 0 ; }