Special Binary String

Hard
1040.

Special Binary String

Special Binary String is a hard coding problem on strings, greedy and recursion, asked in Amazon, Google, Meta and Rubrik interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {string}
 */
var makeLargestSpecial = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Special Binary String — Solution in Python, Java & C++

Special Binary String solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Special Binary String is a hard coding problem on strings, greedy and recursion, asked in Amazon, Google, Meta and Rubrik interviews.

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.

Hints for Special Binary String

  1. Hint 1

    Think of 1 as an opening bracket and 0 as a closing one: a special string is exactly a balanced bracket sequence.

  2. Hint 2

    Split s into its top-level special pieces — each begins where the running balance leaves 0 and ends where it returns to 0.

  3. Hint 3

    Each piece is 1 + inner + 0. Solve inner recursively, then sort the pieces in descending order and concatenate.

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

  1. Walk s, adding 1 for '1' and subtracting 1 for '0'.
  2. Every time the running balance returns to 0, a top-level piece s[start..j] has closed.
  3. Rebuild that piece as "1" + solve(s[start+1..j-1]) + "0".
  4. 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)

Java

public static String makeLargestSpecial(String s) {
    int count = 0, start = 0;
    List<String> subs = new ArrayList<>();
    for (int j = 0; j < s.length(); j++) {
        count += s.charAt(j) == '1' ? 1 : -1;
        if (count == 0) {
            subs.add("1" + makeLargestSpecial(s.substring(start + 1, j)) + "0");
            start = j + 1;
        }
    }
    subs.sort(Collections.reverseOrder());
    StringBuilder sb = new StringBuilder();
    for (String piece : subs) sb.append(piece);
    return sb.toString();
}

C++

string makeLargestSpecial(string s) {
    int count = 0, start = 0;
    vector<string> subs;
    for (int j = 0; j < (int) s.size(); j++) {
        count += s[j] == '1' ? 1 : -1;
        if (count == 0) {
            subs.push_back("1" + makeLargestSpecial(s.substr(start + 1, j - start - 1)) + "0");
            start = j + 1;
        }
    }
    sort(subs.begin(), subs.end(), greater<string>());
    string out;
    for (auto& piece : subs) out += piece;
    return out;
}

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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Greedy Algorithms