text: Form lexicographically smallest string with minimum replacements having equal number of 0 s , 1 s and 2 s | C ++ implementation of the approach ; Function that returns the modified lexicographically smallest string after performing minimum number of given operations ; Stores the initial frequencies of characters 0 s , 1 s and 2 s ; Stores number of processed characters upto that point of each type ; Required number of characters of each type ; If the current type has already reqd number of characters , no need to perform any operation ; Process all 3 cases ; Check for 1 first ; Else 2 ; Here we need to check processed [ 1 ] only for 2 since 0 is less than 1 and we can replace it anytime ; Here we can replace 2 with 0 and 1 anytime ; keep count of processed characters of each type ; Driver Code
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; string formStringMinOperations ( string s ) { int count [ 3 ] = { 0 } ; for ( auto & c : s ) count ++ ; int processed [ 3 ] = { 0 } ; int reqd = ( int ) s . size ( ) / 3 ; for ( int i = 0 ; i < s . size ( ) ; i ++ ) { if ( count [ s [ i ] - '0' ] == reqd ) continue ; if ( s [ i ] == '0' && count [ 0 ] > reqd && processed [ 0 ] >= reqd ) { if ( count [ 1 ] < reqd ) { s [ i ] = '1' ; count [ 1 ] ++ ; count [ 0 ] -- ; } else if ( count [ 2 ] < reqd ) { s [ i ] = '2' ; count [ 2 ] ++ ; count [ 0 ] -- ; } } if ( s [ i ] == '1' && count [ 1 ] > reqd ) { if ( count [ 0 ] < reqd ) { s [ i ] = '0' ; count [ 0 ] ++ ; count [ 1 ] -- ; } else if ( count [ 2 ] < reqd && processed [ 1 ] >= reqd ) { s [ i ] = '2' ; count [ 2 ] ++ ; count [ 1 ] -- ; } } if ( s [ i ] == '2' && count [ 2 ] > reqd ) { if ( count [ 0 ] < reqd ) { s [ i ] = '0' ; count [ 0 ] ++ ; count [ 2 ] -- ; } else if ( count [ 1 ] < reqd ) { s [ i ] = '1' ; count [ 1 ] ++ ; count [ 2 ] -- ; } } processed [ s [ i ] - '0' ] ++ ; } return s ; } int main ( ) { string s = "011200" ; cout << formStringMinOperations ( s ) ; return 0 ; }