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 1s and 0s.
2. Every prefix has at least as many 1s as 0s.

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

Example function shape:

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

Examples

Example 1:

s = "11011000"

Output:

"11100100"

The string can be decomposed into special parts.

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

Swapping them gives a larger string:

11011000 -> 11100100

So the answer is:

"11100100"

Example 2:

s = "10"

Output:

"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:

1 as (
0 as )

Then the rules match exactly:

So a special string has a nested structure.

Every primitive special block looks like:

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.

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

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

Example:

s = "11011000"

Scan:

The whole string is one top-level block.

Its inside is:

101100

Now recursively process that inside.

It decomposes into:

10
1100

Sort descending:

1100
10

Wrap again with outer 1 and 0:

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:

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).

The input length is small enough for this recursive approach.

Implementation

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:

parts = []

The balance counter tracks how deeply nested we are:

balance = 0

When we see 1, we go one level deeper:

balance += 1

When we see 0, we close one level:

balance -= 1

When balance returns to zero:

if balance == 0:

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

The inside of that block is:

s[start + 1:i]

We recursively optimize it:

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

Then we wrap it again:

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

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

parts.sort(reverse=True)

Finally, we join them:

return "".join(parts)

Testing

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: