Maximum Binary String After Change

Med

#1560Time: O(S * N), where S is the number of reachable unique strings. The number of states S can be exponential in N, making the approach too slow for the given constraints.Space: O(S * N), where S is the number of reachable unique strings and N is the length of the string. This is likely to be exponential and thus infeasible.1 company

Patterns

Greedy

Data structures

String

Companies

Huawei

Prompt

You are given a binary string binary consisting of only 0's or 1's. You can apply each of the following operations any number of times:

Operation 1: If the number contains the substring "00", you can replace it with "10".
- For example, "00010" -> "10010"
Operation 2: If the number contains the substring "10", you can replace it with "01".
- For example, "00010" -> "00001"

Return the maximum binary string you can obtain after any number of operations. Binary string x is greater than binary string y if x's decimal representation is greater than y's decimal representation.

Example 1:

Input: binary = "000110"
Output: "111011"
Explanation: A valid transformation sequence can be:
"000110" -> "000101" 
"000101" -> "100101" 
"100101" -> "110101" 
"110101" -> "110011" 
"110011" -> "111011"

Example 2:

Input: binary = "01"
Output: "01"
Explanation: "01" cannot be transformed any further.

Constraints:

1 <= binary.length <= 10⁵
binary consist of '0' and '1'.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach treats the problem as a state-space search. Each unique binary string that can be formed is a state, and the allowed operations ("00" -> "10", "10" -> "01") are transitions between states. We can use a search algorithm like Breadth-First Search (BFS) or Depth-First Search (DFS) to explore all reachable states from the initial string. By keeping track of the lexicographically largest string found during the exploration, we can find the solution. A set is used to store visited states to prevent re-processing and getting stuck in cycles.

Algorithm

Initialize a queue for Breadth-First Search (BFS) with the initial binary string.
Use a HashSet to keep track of all visited strings to avoid cycles and redundant computations.
Initialize a variable maxString with the initial binary string.
While the queue is not empty, dequeue a string s.
Iterate through the string s to find all occurrences of "00" and "10".
For each occurrence, apply the corresponding transformation ("00" -> "10" or "10" -> "01") to generate a newString.
If newString has not been visited: a. Add newString to the queue and the visited set. b. Compare newString with maxString lexicographically and update maxString if newString is larger.
After the BFS completes, maxString will hold the maximum possible binary string.

Walkthrough

The brute-force method systematically explores every possible string that can be generated from the input. Starting with the given binary string, we apply the two operations at every possible position to generate a new set of strings. This process is repeated for each newly generated string until no new strings can be created. We use a queue for a BFS traversal to ensure we explore strings level by level, and a hash set to avoid redundant work on strings we've already seen. Throughout this process, we maintain a variable that stores the lexicographically greatest string encountered so far. While this method is guaranteed to find the correct answer, the number of possible strings can be astronomically large, making it impractical for anything but very small input strings.

Complexity

Time

O(S * N), where S is the number of reachable unique strings. The number of states S can be exponential in N, making the approach too slow for the given constraints.

Space

O(S * N), where S is the number of reachable unique strings and N is the length of the string. This is likely to be exponential and thus infeasible.

Trade-offs

Pros

Guaranteed to find the optimal solution.
Conceptually straightforward application of graph traversal algorithms.

Cons

Extremely high time complexity, making it infeasible for the given constraints.
Requires a large amount of memory to store all visited states, which can lead to memory overflow.

A highly efficient greedy approach can be formulated by analyzing the net effect of the operations. The operation "10" -> "01" allows a '0' to move left past '1's. The operation "00" -> "10" converts two '0's into a '1' and a '0'. This means we can transform all but one '0' into '1's. The leading '1's (before the first '0') cannot be moved. The rest of the string, which contains all the '0's, can be optimally rearranged. By consolidating all '0's, we can convert them into a sequence of '1's followed by a single '0'. This leads to a simple formula to directly construct the final, maximal string.

Algorithm

Count the total number of zeros (zeros) in the input string binary.
If zeros is 0 or 1, no "00" -> "10" transformation is possible. The "10" -> "01" transformation would only yield a lexicographically smaller string. Thus, the string is already maximal. Return the original binary string.
Find the index of the first '0' in the string. Let this be first_zero_idx. This represents the number of leading '1's which are fixed in their positions.
The final string will consist of n-1 ones and a single zero. The key is to determine the position of this zero.
The final zero's position is calculated as final_zero_pos = first_zero_idx + zeros - 1.
Construct the result: create a character array of length n filled with '1's, then set the character at final_zero_pos to '0'.
Convert the character array to a string and return it.

Walkthrough

This optimal approach is based on a key insight: the final maximized string will contain at most one '0'. If the original string has k > 1 zeros, we can use the "00" -> "10" operation k-1 times to convert k-1 zeros into k-1 ones, leaving a single '0'. The "10" -> "01" operation allows us to effectively move this '0' around.

Any '1's at the beginning of the string (before the first '0') are stuck; no operation can move them or place a '0' before them. Let's say there are leading_ones such '1's. The rest of the string contains all the zeros and the remaining ones. This segment can be transformed into a string with zeros - 1 new '1's, all the original '1's from this segment, and one '0'. To maximize the overall string, we should place all possible '1's first. The transformed segment will become a block of '1's followed by a single '0'.

Therefore, the final '0' will be located at an index equal to the count of leading '1's plus the count of newly formed '1's (zeros - 1). This allows us to calculate the final position of the '0' and construct the string in a single pass.

1import java.util.Arrays;2 3class Solution {4    public String maximumBinaryString(String binary) {5        int n = binary.length();6        int zeros = 0;7        int firstZeroIdx = -1;8 9        for (int i = 0; i < n; i++) {10            if (binary.charAt(i) == '0') {11                zeros++;12                if (firstZeroIdx == -1) {13                    firstZeroIdx = i;14                }15            }16        }17 18        // If there are 0 or 1 zeros, the string cannot be improved.19        // "00"->"10" is not possible. "10"->"01" makes the string smaller.20        if (zeros <= 1) {21            return binary;22        }23 24        // The final string will have n-1 ones and one zero.25        // We need to find the position of this single zero.26        char[] resultChars = new char[n];27        Arrays.fill(resultChars, '1');28        29        // The zero will be placed after the leading ones and after the newly created ones.30        // Number of leading ones = firstZeroIdx.31        // Number of newly created ones = zeros - 1.32        int finalZeroPos = firstZeroIdx + zeros - 1;33        resultChars[finalZeroPos] = '0';34 35        return new String(resultChars);36    }37}

Complexity

Time

O(N), where N is the length of the binary string. We perform a single pass to count zeros and find the first zero, and another pass to construct the result string.

Space

O(N) to store the character array for the result string. In Java, strings are immutable, so this space is necessary for the output.

Trade-offs

Pros

Extremely efficient with linear time complexity.
Low space complexity.
Simple to implement once the pattern is understood.

Cons

The logic is not immediately obvious and requires careful analysis of the operations' effects.

Solutions

Solution

1class Solution {2public3  String maximumBinaryString(String binary) {4    int k = binary.indexOf('0');5    if (k == -1) {6      return binary;7    }8    int n = binary.length();9    for (int i = k + 1; i < n; ++i) {10      if (binary.charAt(i) == '0') {11        ++k;12      }13    }14    char[] ans = binary.toCharArray();15    Arrays.fill(ans, '1');16    ans[k] = '0';17    return String.valueOf(ans);18  }19}

1public class Solution {2    public string MaximumBinaryString(string binary) {3        int k = binary.IndexOf('0');4        if (k == -1) {5            return binary;6        }7        k += binary.Substring(k + 1).Count(c => c == '0');8        return new string('1', k) + '0' + new string('1', binary.Length - k - 1);9    }10}

1class Solution { public: string maximumBinaryString ( string binary ) { int k = binary . find ( '0' ); if ( k == binary . npos ) return binary ; int n = binary . size (); for ( int i = k + 1 ; i < n ; ++ i ) { if ( binary [ i ] == '0' ) { ++ k ; } } return string ( k , '1' ) + '0' + string ( n - k - 1 , '1' ); } };

1class Solution:2    def maximumBinaryString(self, binary: str) -> str: k = binary . find('0') if k == - 1: return binary k += binary[k + 1:]. count('0') return '1' * k + '0' + '1' * (len(binary) - k - 1)

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem