# LeetCode 761: Special Binary String

## Problem Restatement

A special binary string is a binary string with two properties:

1. It has the same number of `1`s and `0`s.
2. Every prefix has at least as many `1`s as `0`s.

We are given a special binary string `s`.

One move lets us choose two consecutive non-empty special substrings and swap them.

We need to return the lexicographically largest string possible after applying any number of moves.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A special binary string `s` |
| Output | The lexicographically largest string possible |
| Move | Swap two adjacent non-empty special substrings |
| Guarantee | `s` is already special |

Example function shape:

```python
def makeLargestSpecial(s: str) -> str:
    ...
```

## Examples

Example 1:

```python
s = "11011000"
```

Output:

```python
"11100100"
```

The string can be decomposed into special parts.

Inside it, `"10"` and `"1100"` are consecutive special substrings.

Swapping them gives a larger string:

```text
11011000 -> 11100100
```

So the answer is:

```python
"11100100"
```

Example 2:

```python
s = "10"
```

Output:

```python
"10"
```

There is only one special substring. No useful swap can make it larger.

## First Thought: Try Every Swap

One direct idea is to try all possible swaps of adjacent special substrings.

After each swap, we could repeat the process and remember the largest string seen.

This is too expensive.

There may be many ways to split a string into special substrings, and swaps can create many intermediate strings.

We need to use the structure of special strings instead.

## Key Insight

A special binary string behaves like a valid parentheses string.

Think of:

```text
1 as (
0 as )
```

Then the rules match exactly:

| Binary rule | Parentheses rule |
|---|---|
| Same number of `1`s and `0`s | Same number of opening and closing parentheses |
| Every prefix has at least as many `1`s as `0`s | Every prefix has at least as many opening parentheses as closing parentheses |

So a special string has a nested structure.

Every primitive special block looks like:

```text
1 + inner_special_string + 0
```

The top-level string may be a concatenation of several such blocks.

To make the whole string lexicographically largest:

1. Recursively make each inner block largest.
2. Sort the top-level blocks in descending lexicographic order.
3. Join them together.

## Decomposing the String

We scan the string with a balance counter.

```python
balance += 1 if ch == "1" else -1
```

A top-level special substring ends when `balance` returns to `0`.

Example:

```text
s = "11011000"
```

Scan:

| Index | Character | Balance |
|---:|---|---:|
| `0` | `1` | `1` |
| `1` | `1` | `2` |
| `2` | `0` | `1` |
| `3` | `1` | `2` |
| `4` | `1` | `3` |
| `5` | `0` | `2` |
| `6` | `0` | `1` |
| `7` | `0` | `0` |

The whole string is one top-level block.

Its inside is:

```text
101100
```

Now recursively process that inside.

It decomposes into:

```text
10
1100
```

Sort descending:

```text
1100
10
```

Wrap again with outer `1` and `0`:

```text
1 + 110010 + 0 = 11100100
```

## Algorithm

1. Create an empty list `parts`.
2. Scan `s` with a balance counter.
3. Whenever balance returns to `0`, we found one top-level special block:
   1. Remove its outer `1` and `0`.
   2. Recursively make the inner string largest.
   3. Wrap it back as `"1" + inner + "0"`.
   4. Add it to `parts`.
4. Sort `parts` in descending order.
5. Return the joined result.

## Correctness

Every time the balance returns to zero, the scanned substring is a complete top-level special substring. These substrings are consecutive and together form the whole input string.

A move can swap consecutive special substrings, so at the same nesting level we may reorder these top-level special blocks. To make the string lexicographically largest, those blocks should appear in descending lexicographic order.

Each block has the form:

```text
1 + inner + 0
```

The outer `1` and `0` must stay as the boundary of that block. Any improvement inside the block must come from rearranging the inner special string. The recursive call produces the largest possible inner string.

After each inner block is maximized, sorting the resulting top-level blocks in descending order gives the largest possible concatenation at that level.

The base case is an empty string or a block with no inner content. It is already optimal.

By applying this argument recursively at every nesting level, the algorithm returns the lexicographically largest string reachable by valid swaps.

## Complexity

Let `n = len(s)`.

| Metric | Value | Why |
|---|---|---|
| Time | `O(n^2)` | Recursion and string sorting/comparison may compare substrings |
| Space | `O(n)` | Recursion stack and temporary parts store substrings |

The input length is small enough for this recursive approach.

## Implementation

```python
class Solution:
    def makeLargestSpecial(self, s: str) -> str:
        parts = []
        balance = 0
        start = 0

        for i, ch in enumerate(s):
            if ch == "1":
                balance += 1
            else:
                balance -= 1

            if balance == 0:
                inner = self.makeLargestSpecial(s[start + 1:i])
                parts.append("1" + inner + "0")
                start = i + 1

        parts.sort(reverse=True)
        return "".join(parts)
```

## Code Explanation

We store top-level special blocks here:

```python
parts = []
```

The balance counter tracks how deeply nested we are:

```python
balance = 0
```

When we see `1`, we go one level deeper:

```python
balance += 1
```

When we see `0`, we close one level:

```python
balance -= 1
```

When balance returns to zero:

```python
if balance == 0:
```

we have found one complete top-level special block from `start` to `i`.

The inside of that block is:

```python
s[start + 1:i]
```

We recursively optimize it:

```python
inner = self.makeLargestSpecial(s[start + 1:i])
```

Then we wrap it again:

```python
parts.append("1" + inner + "0")
```

After collecting all top-level parts, we sort them from largest to smallest:

```python
parts.sort(reverse=True)
```

Finally, we join them:

```python
return "".join(parts)
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.makeLargestSpecial("11011000") == "11100100"
    assert s.makeLargestSpecial("10") == "10"
    assert s.makeLargestSpecial("1010") == "1010"
    assert s.makeLargestSpecial("1100") == "1100"
    assert s.makeLargestSpecial("111000") == "111000"

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `"11011000"` | Main example with useful inner swap |
| `"10"` | Smallest non-empty special string |
| `"1010"` | Two equal simple blocks |
| `"1100"` | Nested block already optimal |
| `"111000"` | Deep nesting already optimal |