text: 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
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; string lexicographicallyMaximum ( string S , int N ) { unordered_map < char , int > M ; for ( int i = 0 ; i < N ; ++ i ) { M [ S [ i ] ] ++ ; } vector < char > V ; for ( char i = ' a ' ; i < ( char ) ( ' a ' + min ( N , 25 ) ) ; ++ i ) { if ( M [ i ] == 0 ) { V . push_back ( i ) ; } } int j = V . size ( ) - 1 ; for ( int i = 0 ; i < N ; ++ i ) { if ( S [ i ] >= ( ' a ' + min ( N , 25 ) ) M [ S [ i ] ] > 1 ) { if ( V [ j ] < S [ i ] ) continue ; M [ S [ i ] ] -- ; S [ i ] = V [ j ] ; j -- ; } if ( j < 0 ) break ; } int l = 0 ; for ( int i = N - 1 ; i >= 0 ; i -- ) { if ( l > j ) break ; if ( S [ i ] >= ( ' a ' + min ( N , 25 ) ) M [ S [ i ] ] > 1 ) { M [ S [ i ] ] -- ; S [ i ] = V [ l ] ; l ++ ; } } return S ; } int main ( ) { string S = " abccefghh " ; int N = S . length ( ) ; cout << lexicographicallyMaximum ( S , N ) ; return 0 ; }