Special Binary String — Hard Problem & Solution

A binary string is special when it has an equal number of 0s and 1s and every prefix has at least as many 1s as 0s.

Difficulty: Hard
Topics: Strings, Greedy, Divide and Conquer, Recursion
Asked at: Amazon, Google, Meta
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A binary string is special when it has an equal number of 0s and 1s and every prefix has at least as many 1s as 0s.

You may repeatedly choose two consecutive, non-empty, special substrings of s and swap them. Return the lexicographically largest string reachable.

Example 1

Input: s = "11011000"
Output: 11100100
Explanation: The two inner special pieces `10` and `1100` swap, putting the larger one first.

Example 2

Input: s = "101100"
Output: 110010
Explanation: `10` and `1100` are consecutive special substrings; swapping them wins.

Example 3

Input: s = "10"
Output: 10
Explanation: Nothing to swap.

Constraints

1 <= s.length <= 50
s[i] is either '0' or '1'.
s is a special binary string.

How to solve Special Binary String

Read the string as balanced brackets. Split it into top-level special pieces, recursively make each piece's interior as large as possible, then sort the pieces descending and join them.

Approach

Walk s, adding 1 for '1' and subtracting 1 for '0'.
Every time the running balance returns to 0, a top-level piece s[start..j] has closed.
Rebuild that piece as "1" + solve(s[start+1..j-1]) + "0".
Sort the pieces in descending lexicographic order and concatenate them.

Why it works

The swap operation is exactly "reorder sibling pieces", so at every nesting level the pieces are freely permutable and the largest-first order is optimal. Recursing into the interior first is what makes the sort correct: comparing two pieces only decides the answer once each is already in its own best form. And because every piece starts with 1 and ends with 0, no piece is a prefix of another, so the descending sort has no ties to break.

Complexity

Time — O(n² log n) in the worst case, from string building and sorting at each level
Space — O(n²) across the recursion

Pitfalls

Sort the pieces after recursing into them, not before.
The recursive call takes the strict interior s[start+1..j-1], not the whole piece — otherwise it never terminates.
Sorting ascending and reversing is the same as descending here, but a plain ascending sort is the common slip.

Reference solution

Python

def makeLargestSpecial(s: str) -> str:
    count = 0
    start = 0
    subs = []
    for j, c in enumerate(s):
        count += 1 if c == "1" else -1
        if count == 0:
            subs.append("1" + makeLargestSpecial(s[start + 1:j]) + "0")
            start = j + 1
    subs.sort(reverse=True)
    return "".join(subs)

JavaScript

var makeLargestSpecial = function(s) {
    var count = 0, start = 0;
    var subs = [];
    for (var j = 0; j < s.length; j++) {
        count += s.charAt(j) === "1" ? 1 : -1;
        if (count === 0) {
            subs.push("1" + makeLargestSpecial(s.substring(start + 1, j)) + "0");
            start = j + 1;
        }
    }
    subs.sort();
    subs.reverse();
    return subs.join("");
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 282 strings problems · the whole catalogue