Special Binary String

Hard Recursion & Backtracking Divide and Conquer Original on LeetCode

Reported atNvidiaRubrik

Special Binary String is a hard recursion & backtracking problem solved with the divide and conquer pattern. The best approach, optimal (recursive split and sort), runs in O(n²) time and O(n²) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (keep swapping while it helps) up.

Problem

A binary string is special when it has as many 1s as 0s and every prefix has at least as many 1s as 0s (read 1 as an opening bracket and 0 as a closing one: the string is balanced).

You are given a special string s. In one move you may pick two adjacent, non-empty special substrings of s and swap them. Return the lexicographically largest string you can reach with any number of moves.

Examples

Example 1

Input
s = "1100110100"
Output
"1101001100"
Why
s is "1100" followed by "110100". Swapping these two neighbouring special pieces puts the larger one first.

Example 2

Input
s = "10110100"
Output
"11010010"
Why
Swap "10" with "110100"; no further swap makes the string larger.

Example 3

Input
s = "1100"
Output
"1100"
Why
The only possible split is the string itself, so nothing can move.

Constraints

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

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 14 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (keep swapping while it helps)O(n⁴) per swap, many swapsO(n)
Optimal (recursive split and sort)O(n²)O(n²)

1Brute force (keep swapping while it helps)

TimeO(n⁴) per swap, many swapsEach scan tries O(n³) pairs (X, Y) and compares strings of length up to n; the number of swaps is bounded but can be large.
SpaceO(n)The temporary strings built for each comparison.

Scan for two neighbouring special substrings X and Y. If Y + X is larger than X + Y, swap them and start over. Each swap makes the string strictly larger, so this stops, and when no swap helps the string is the largest one.

  1. For every start i, extend j while the balance stays >= 0; whenever it returns to 0, s[i..j] is a special X.
  2. From j + 1, find every special Y the same way.
  3. If Y + X > X + Y, rebuild s with the two swapped and repeat from the beginning.
  4. When a full scan finds no improving swap, return s.
class Solution {
    public String makeLargestSpecial(String s) {
        String next = swapOnce(s);
        while (next != null) {
            s = next;
            next = swapOnce(s);
        }
        return s;
    }

    private String swapOnce(String s) {
        int n = s.length();
        for (int i = 0; i < n; i++) {
            int bal = 0;
            for (int j = i; j < n; j++) {
                bal += s.charAt(j) == '1' ? 1 : -1;
                if (bal < 0) break;
                if (bal != 0) continue;
                int bal2 = 0;
                for (int k = j + 1; k < n; k++) {
                    bal2 += s.charAt(k) == '1' ? 1 : -1;
                    if (bal2 < 0) break;
                    if (bal2 != 0) continue;
                    String x = s.substring(i, j + 1), y = s.substring(j + 1, k + 1);
                    if ((y + x).compareTo(x + y) > 0) {
                        return s.substring(0, i) + y + x + s.substring(k + 1);
                    }
                }
            }
        }
        return null;
    }
}

2Optimal (recursive split and sort)

TimeO(n²)Each nesting level does linear work plus a sort of its pieces; with n <= 50 levels the total is at most quadratic (times a small log factor).
SpaceO(n²)Substrings are created at each recursion level.

Split s into top-level pieces where the running balance returns to 0. Each piece is 1 + inner + 0 with a special inner part, and a swap can never move characters across the outer 1 and 0 of a piece. So: make each inner part largest recursively, wrap it back in 1…0, and sort the pieces in descending order before joining them.

  1. Walk s tracking the balance; each time it reaches 0, the piece s[start..i] is complete.
  2. For that piece, recursively solve the inner part s[start + 1..i - 1] and store "1" + result + "0".
  3. Sort the stored pieces in descending lexicographic order and join them.
class Solution {
    public String makeLargestSpecial(String s) {
        List<String> parts = new ArrayList<>();
        int bal = 0, start = 0;
        for (int i = 0; i < s.length(); i++) {
            bal += s.charAt(i) == '1' ? 1 : -1;
            if (bal == 0) {
                parts.add("1" + makeLargestSpecial(s.substring(start + 1, i)) + "0");
                start = i + 1;
            }
        }
        parts.sort(Collections.reverseOrder());
        return String.join("", parts);
    }
}

Edge cases to test

  • The smallest string "10"
  • A string that is already the largest (answer equals the input)
  • Many equal pieces like "101010"
  • Deep nesting where the improvement happens inside an outer 1…0 pair

Hints

Hint 1

Treat 1 as "(" and 0 as ")". A special string is then a balanced parenthesis string.

Hint 2

Split s into its top-level pieces (each piece returns the balance to 0). Each piece looks like 1 + inner + 0, where inner is again special.

Hint 3

Make every inner part as large as possible first, then put the pieces in descending order.

FAQ

What is the best time complexity for Special Binary String?

Optimal (recursive split and sort) runs in O(n²) time and O(n²) extra space. Each nesting level does linear work plus a sort of its pieces; with n <= 50 levels the total is at most quadratic (times a small log factor).

Which pattern does Special Binary String use?

It is a recursion & backtracking problem that uses the divide and conquer pattern. Other problems with the same pattern: Construct Quad Tree.

Is there a brute force solution for Special Binary String?

Yes. Brute force (keep swapping while it helps) takes O(n⁴) per swap, many swaps time and O(n) space. Scan for two neighbouring special substrings X and Y.

Which edge cases should I test for Special Binary String?

The smallest string "10"; A string that is already the largest (answer equals the input); Many equal pieces like "101010"; Deep nesting where the improvement happens inside an outer 1…0 pair.