Lexicographically largest string possible in one swap | Java 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 ; Function to reverse array ; Driver Code
import java . util . * ; import java . lang . * ; class GFG { static String findLargest ( StringBuilder 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 . charAt ( i ) - ' a ' ; if ( loccur [ chI ] == - 1 ) { loccur [ chI ] = i ; } } char [ ] sorted_s = s . toString ( ) . toCharArray ( ) ; Arrays . sort ( sorted_s ) ; reverse ( sorted_s ) ; for ( int i = 0 ; i < len ; ++ i ) { if ( s . charAt ( i ) != sorted_s [ i ] ) { int chI = sorted_s [ i ] - ' a ' ; int last_occ = loccur [ chI ] ; char tmp = s . charAt ( i ) ; s . setCharAt ( i , s . charAt ( last_occ ) ) ; s . setCharAt ( last_occ , tmp ) ; break ; } } return s . toString ( ) ; } static void reverse ( char a [ ] ) { int i , n = a . length ; for ( i = 0 ; i < n / 2 ; i ++ ) { char t = a [ i ] ; a [ i ] = a [ n - i - 1 ] ; a [ n - i - 1 ] = t ; } } public static void main ( String [ ] args ) { StringBuilder s = new StringBuilder ( " yrstvw " ) ; System . out . println ( findLargest ( s ) ) ; } }