Special Binary String
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 <= 50s[i]is'0'or'1'.sis 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.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
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.
| Approach | Time | Space |
|---|---|---|
| Brute force (keep swapping while it helps) | O(n⁴) per swap, many swaps | O(n) |
| Optimal (recursive split and sort) | O(n²) | O(n²) |
1Brute force (keep swapping while it helps)
O(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.O(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.
- For every start i, extend j while the balance stays >= 0; whenever it returns to 0, s[i..j] is a special X.
- From j + 1, find every special Y the same way.
- If Y + X > X + Y, rebuild s with the two swapped and repeat from the beginning.
- 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;
}
}class Solution:
def makeLargestSpecial(self, s: str) -> str:
def swap_once(s):
n = len(s)
for i in range(n):
bal = 0
for j in range(i, n):
bal += 1 if s[j] == "1" else -1
if bal < 0:
break
if bal != 0:
continue
bal2 = 0
for k in range(j + 1, n):
bal2 += 1 if s[k] == "1" else -1
if bal2 < 0:
break
if bal2 != 0:
continue
x, y = s[i:j + 1], s[j + 1:k + 1]
if y + x > x + y:
return s[:i] + y + x + s[k + 1:]
return None
nxt = swap_once(s)
while nxt is not None:
s = nxt
nxt = swap_once(s)
return sclass Solution {
bool swapOnce(string& s) {
int n = s.size();
for (int i = 0; i < n; i++) {
int bal = 0;
for (int j = i; j < n; j++) {
bal += s[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[k] == '1' ? 1 : -1;
if (bal2 < 0) break;
if (bal2 != 0) continue;
string x = s.substr(i, j - i + 1), y = s.substr(j + 1, k - j);
if (y + x > x + y) {
s = s.substr(0, i) + y + x + s.substr(k + 1);
return true;
}
}
}
}
return false;
}
public:
string makeLargestSpecial(string s) {
while (swapOnce(s)) {
}
return s;
}
};function makeLargestSpecial(s) {
const swapOnce = (s) => {
const n = s.length;
for (let i = 0; i < n; i++) {
let bal = 0;
for (let j = i; j < n; j++) {
bal += s[j] === "1" ? 1 : -1;
if (bal < 0) break;
if (bal !== 0) continue;
let bal2 = 0;
for (let k = j + 1; k < n; k++) {
bal2 += s[k] === "1" ? 1 : -1;
if (bal2 < 0) break;
if (bal2 !== 0) continue;
const x = s.slice(i, j + 1), y = s.slice(j + 1, k + 1);
if (y + x > x + y) return s.slice(0, i) + y + x + s.slice(k + 1);
}
}
}
return null;
};
let next = swapOnce(s);
while (next !== null) {
s = next;
next = swapOnce(s);
}
return s;
}2Optimal (recursive split and sort)
O(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).O(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.
- Walk s tracking the balance; each time it reaches 0, the piece s[start..i] is complete.
- For that piece, recursively solve the inner part s[start + 1..i - 1] and store "1" + result + "0".
- 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);
}
}class Solution:
def makeLargestSpecial(self, s: str) -> str:
parts = []
bal = 0
start = 0
for i, c in enumerate(s):
bal += 1 if c == "1" else -1
if bal == 0:
parts.append("1" + self.makeLargestSpecial(s[start + 1:i]) + "0")
start = i + 1
parts.sort(reverse=True)
return "".join(parts)class Solution {
public:
string makeLargestSpecial(string s) {
vector<string> parts;
int bal = 0, start = 0;
for (int i = 0; i < (int)s.size(); i++) {
bal += s[i] == '1' ? 1 : -1;
if (bal == 0) {
parts.push_back("1" + makeLargestSpecial(s.substr(start + 1, i - start - 1)) + "0");
start = i + 1;
}
}
sort(parts.begin(), parts.end(), greater<string>());
string out;
for (const string& p : parts) out += p;
return out;
}
};function makeLargestSpecial(s) {
const parts = [];
let bal = 0, start = 0;
for (let i = 0; i < s.length; i++) {
bal += s[i] === "1" ? 1 : -1;
if (bal === 0) {
parts.push("1" + makeLargestSpecial(s.slice(start + 1, i)) + "0");
start = i + 1;
}
}
parts.sort();
parts.reverse();
return parts.join("");
}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.