Form lexicographically smallest string with minimum replacements having equal number of 0 s , 1 s and 2 s | Python3 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
import math NEW_LINE def formStringMinOperations ( ss ) : NEW_LINE INDENT count = [ 0 ] * 3 ; NEW_LINE s = list ( ss ) ; NEW_LINE for i in range ( len ( s ) ) : NEW_LINE INDENT count [ ord ( s [ i ] ) - ord ( '0' ) ] += 1 ; NEW_LINE DEDENT processed = [ 0 ] * 3 ; NEW_LINE reqd = math . floor ( len ( s ) / 3 ) ; NEW_LINE for i in range ( len ( s ) ) : NEW_LINE INDENT if ( count [ ord ( s [ i ] ) - ord ( '0' ) ] == reqd ) : NEW_LINE INDENT continue ; NEW_LINE DEDENT if ( s [ i ] == '0' and count [ 0 ] > reqd and processed [ 0 ] >= reqd ) : NEW_LINE INDENT if ( count [ 1 ] < reqd ) : NEW_LINE INDENT s [ i ] = '1' ; NEW_LINE count [ 1 ] += 1 ; NEW_LINE count [ 0 ] -= 1 ; NEW_LINE DEDENT elif ( count [ 2 ] < reqd ) : NEW_LINE INDENT s [ i ] = '2' ; NEW_LINE count [ 2 ] += 1 ; NEW_LINE count [ 0 ] -= 1 ; NEW_LINE DEDENT DEDENT if ( s [ i ] == '1' and count [ 1 ] > reqd ) : NEW_LINE INDENT if ( count [ 0 ] < reqd ) : NEW_LINE INDENT s [ i ] = '0' ; NEW_LINE count [ 0 ] += 1 ; NEW_LINE count [ 1 ] -= 1 ; NEW_LINE DEDENT elif ( count [ 2 ] < reqd and processed [ 1 ] >= reqd ) : NEW_LINE INDENT s [ i ] = '2' ; NEW_LINE count [ 2 ] += 1 ; NEW_LINE count [ 1 ] -= 1 ; NEW_LINE DEDENT DEDENT if ( s [ i ] == '2' and count [ 2 ] > reqd ) : NEW_LINE INDENT if ( count [ 0 ] < reqd ) : NEW_LINE INDENT s [ i ] = '0' ; NEW_LINE count [ 0 ] += 1 ; NEW_LINE count [ 2 ] -= 1 ; NEW_LINE DEDENT elif ( count [ 1 ] < reqd ) : NEW_LINE INDENT s [ i ] = '1' ; NEW_LINE count [ 1 ] += 1 ; NEW_LINE count [ 2 ] -= 1 ; NEW_LINE DEDENT DEDENT processed [ ord ( s [ i ] ) - ord ( '0' ) ] += 1 ; NEW_LINE DEDENT return ' ' . join ( s ) ; NEW_LINE DEDENT s = "011200" ; NEW_LINE print ( formStringMinOperations ( s ) ) ; NEW_LINE