Form lexicographically smallest string with minimum replacements having equal number of 0 s , 1 s and 2 s | Java 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
class GFG { static String formStringMinOperations ( char [ ] s ) { int count [ ] = new int [ 3 ] ; for ( char c : s ) { count [ ( int ) c - 48 ] += 1 ; } int processed [ ] = new int [ 3 ] ; int reqd = ( int ) s . length / 3 ; for ( int i = 0 ; i < s . length ; 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 String . valueOf ( s ) ; } public static void main ( String [ ] args ) { String s = "011200" ; System . out . println ( formStringMinOperations ( s . toCharArray ( ) ) ) ; } }