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 Code
using System ; using System . Collections . Generic ; class GFG { static string findLargest ( char [ ] s ) { int len = s . Length ; int [ ] loccur = new int [ 26 ] ; Array . 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 = ( new string ( s ) ) . ToCharArray ( ) ; Array . Sort ( sorted_s ) ; Array . Reverse ( 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 [ i ] ; s [ i ] = s [ last_occ ] ; s [ last_occ ] = temp ; break ; } } return ( new string ( s ) ) ; } static void Main ( ) { string str = " yrstvw " ; char [ ] s = str . ToCharArray ( ) ; Console . WriteLine ( findLargest ( s ) ) ; } }