Lexicographically largest string formed in minimum moves by replacing characters of given String | C # 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
using System ; using System . Collections . Generic ; class GFG { static string lexicographicallyMaximum ( string S , int N ) { Dictionary < char , int > M = new Dictionary < char , int > ( ) ; for ( int i = 0 ; i < N ; ++ i ) { if ( M . ContainsKey ( S [ i ] ) ) M [ S [ i ] ] ++ ; else M . Add ( S [ i ] , 1 ) ; } List < char > V = new List < char > ( ) ; for ( char i = ' a ' ; i < ( char ) ( ' a ' + Math . Min ( N , 25 ) ) ; ++ i ) { if ( M . ContainsKey ( i ) == false ) { V . Add ( i ) ; } } int j = V . Count - 1 ; for ( int i = 0 ; i < N ; ++ i ) { if ( S [ i ] >= ( ' a ' + Math . Min ( N , 25 ) ) || ( M . ContainsKey ( S [ i ] ) && M [ S [ i ] ] > 1 ) ) { if ( V [ j ] < S [ i ] ) continue ; M [ S [ i ] ] -- ; S = S . Substring ( 0 , i ) + V [ 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 [ i ] >= ( ' a ' + Math . Min ( N , 25 ) ) || M . ContainsKey ( S [ i ] ) && M [ S [ i ] ] > 1 ) { M [ S [ i ] ] -- ; S = S . Substring ( 0 , i ) + V [ l ] + S . Substring ( i + 1 ) ; l ++ ; } } return S ; } public static void Main ( ) { string S = " abccefghh " ; int N = S . Length ; Console . Write ( lexicographicallyMaximum ( S , N ) ) ; } }