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.
- Difficulty: Hard
- Topics: Strings, Greedy, Recursion, Divide and Conquer
- Asked at: Amazon, Google, Meta, Rubrik
- 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 <= 50s[i] is either '0' or '1'.s is a special binary string.
Hints for Special Binary String
Hint 1
Think of
1as an opening bracket and0as a closing one: a special string is exactly a balanced bracket sequence.Hint 2
Split
sinto its top-level special pieces — each begins where the running balance leaves 0 and ends where it returns to 0.Hint 3
Each piece is
1 + inner + 0. Solveinnerrecursively, 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
- 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)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