# Maximum Binary String After Change
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-binary-string-after-change)
Canonical: https://scaleengineer.com/dsa/problems/maximum-binary-string-after-change
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** String
**Companies:** [Huawei](https://scaleengineer.com/companies/huawei)
---
## Problem
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 <= 105`
* `binary` consist of `'0'` and `'1'`.

# Approaches
## Brute-Force State-Space Search
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.
**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.
**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.
### Explanation
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.
### Algorithm
1. Initialize a queue for Breadth-First Search (BFS) with the initial `binary` string.
2. Use a `HashSet` to keep track of all visited strings to avoid cycles and redundant computations.
3. Initialize a variable `maxString` with the initial `binary` string.
4. While the queue is not empty, dequeue a string `s`.
5. Iterate through the string `s` to find all occurrences of `"00"` and `"10"`.
6. For each occurrence, apply the corresponding transformation (`"00" -> "10"` or `"10" -> "01"`) to generate a `newString`.
7. 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.
8. After the BFS completes, `maxString` will hold the maximum possible binary string.

## One-Pass Greedy Construction
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.
**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.
**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.
### Explanation
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.

```java
import java.util.Arrays;

class Solution {
    public String maximumBinaryString(String binary) {
        int n = binary.length();
        int zeros = 0;
        int firstZeroIdx = -1;

        for (int i = 0; i < n; i++) {
            if (binary.charAt(i) == '0') {
                zeros++;
                if (firstZeroIdx == -1) {
                    firstZeroIdx = i;
                }
            }
        }

        // If there are 0 or 1 zeros, the string cannot be improved.
        // "00"->"10" is not possible. "10"->"01" makes the string smaller.
        if (zeros <= 1) {
            return binary;
        }

        // The final string will have n-1 ones and one zero.
        // We need to find the position of this single zero.
        char[] resultChars = new char[n];
        Arrays.fill(resultChars, '1');
        
        // The zero will be placed after the leading ones and after the newly created ones.
        // Number of leading ones = firstZeroIdx.
        // Number of newly created ones = zeros - 1.
        int finalZeroPos = firstZeroIdx + zeros - 1;
        resultChars[finalZeroPos] = '0';

        return new String(resultChars);
    }
}
```
### Algorithm
1. Count the total number of zeros (`zeros`) in the input string `binary`.
2. 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.
3. 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.
4. The final string will consist of `n-1` ones and a single zero. The key is to determine the position of this zero.
5. The final zero's position is calculated as `final_zero_pos = first_zero_idx + zeros - 1`.
6. Construct the result: create a character array of length `n` filled with '1's, then set the character at `final_zero_pos` to '0'.
7. Convert the character array to a string and return it.

# Solutions
### Java

```java
class Solution {
public
  String maximumBinaryString(String binary) {
    int k = binary.indexOf('0');
    if (k == -1) {
      return binary;
    }
    int n = binary.length();
    for (int i = k + 1; i < n; ++i) {
      if (binary.charAt(i) == '0') {
        ++k;
      }
    }
    char[] ans = binary.toCharArray();
    Arrays.fill(ans, '1');
    ans[k] = '0';
    return String.valueOf(ans);
  }
}

```

### CSharp

```csharp
public class Solution {
    public string MaximumBinaryString(string binary) {
        int k = binary.IndexOf('0');
        if (k == -1) {
            return binary;
        }
        k += binary.Substring(k + 1).Count(c => c == '0');
        return new string('1', k) + '0' + new string('1', binary.Length - k - 1);
    }
}
```

### CPP

```cpp
class 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' ); } };
```

### Python

```python
class Solution:
    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)

```