Lexicographically largest string formed in minimum moves by replacing characters of given String | Java program for the above approach ; Function to print the lexicographically the largest string obtained in process of obtaining a string containing first N lower case english alphabtes ; Store the frequency of each character ; Traverse the string S ; Stores the characters which are not appearing in S ; Stores the index of the largest character in the array V , that need to be replaced ; Traverse the string , S ; If frequency of S [ i ] is greater than 1 or it is outside the range ; Decrement its frequency by 1 ; Update S [ i ] ; Decrement j by 1 ; Traverse the string , S ; Decrement its frequency by 1 ; Update S [ i ] ; Increment l by 1 ; Return S ; Driver Code ; Given Input ; Function Call
import java . util . * ; public class Main { static String lexicographicallyMaximum ( String S , int N ) { HashMap < Character , Integer > M = new HashMap < > ( ) ; for ( int i = 0 ; i < N ; ++ i ) { if ( M . containsKey ( S . charAt ( i ) ) ) M . put ( S . charAt ( i ) , M . get ( S . charAt ( i ) ) + 1 ) ; else M . put ( S . charAt ( i ) , 1 ) ; } Vector < Character > V = new Vector < Character > ( ) ; for ( char i = ' a ' ; i < ( char ) ( ' a ' + Math . min ( N , 25 ) ) ; ++ i ) { if ( M . containsKey ( i ) == false ) { V . add ( i ) ; } } int j = V . size ( ) - 1 ; for ( int i = 0 ; i < N ; ++ i ) { if ( S . charAt ( i ) >= ( ' a ' + Math . min ( N , 25 ) ) || ( M . containsKey ( S . charAt ( i ) ) && M . get ( S . charAt ( i ) ) > 1 ) ) { if ( V . get ( j ) < S . charAt ( i ) ) continue ; M . put ( S . charAt ( i ) , M . get ( S . charAt ( i ) ) - 1 ) ; S = S . substring ( 0 , i ) + V . get ( j ) + S . substring ( i + 1 ) ; j -- ; } if ( j < 0 ) break ; } int l = 0 ; for ( int i = N - 1 ; i >= 0 ; i -- ) { if ( l > j ) break ; if ( S . charAt ( i ) >= ( ' a ' + Math . min ( N , 25 ) ) || M . containsKey ( S . charAt ( i ) ) && M . get ( S . charAt ( i ) ) > 1 ) { M . put ( S . charAt ( i ) , M . get ( S . charAt ( i ) ) - 1 ) ; S = S . substring ( 0 , i ) + V . get ( l ) + S . substring ( i + 1 ) ; l ++ ; } } return S ; } public static void main ( String [ ] args ) { String S = " abccefghh " ; int N = S . length ( ) ; System . out . println ( lexicographicallyMaximum ( S , N ) ) ; } }