Special Binary String
Problem
A special binary string has equal numbers of 0s and 1s and every prefix has at least as many 1s as 0s. Repeatedly swap adjacent special substrings to produce the lexicographically largest possible string.
s='11011000''11100100'def makeLargestSpecial(s):
count = i = 0
parts = []
for j, c in enumerate(s):
count += 1 if c == '1' else -1
if count == 0:
parts.append('1' + makeLargestSpecial(s[i+1:j]) + '0')
i = j+1
parts.sort(reverse=True)
return "".join(parts)function makeLargestSpecial(s) {
let count = 0, i = 0;
const parts = [];
for (let j = 0; j < s.length; j++) {
count += s[j] === '1' ? 1 : -1;
if (count === 0) {
parts.push('1' + makeLargestSpecial(s.slice(i+1, j)) + '0');
i = j+1;
}
}
parts.sort().reverse();
return parts.join("");
}String makeLargestSpecial(String s) {
int count = 0, i = 0;
List<String> parts = new ArrayList<>();
for (int j = 0; j < s.length(); j++) {
count += s.charAt(j) == '1' ? 1 : -1;
if (count == 0) {
parts.add("1" + makeLargestSpecial(s.substring(i+1, j)) + "0");
i = j+1;
}
}
parts.sort(Comparator.reverseOrder());
StringBuilder sb = new StringBuilder();
for (String p : parts) sb.append(p);
return sb.toString();
}string makeLargestSpecial(string s) {
int count = 0, i = 0;
vector<string> parts;
for (int j = 0; j < (int)s.size(); j++) {
count += s[j] == '1' ? 1 : -1;
if (count == 0) {
parts.push_back("1" + makeLargestSpecial(s.substr(i+1, j-i-1)) + "0");
i = j+1;
}
}
sort(parts.begin(), parts.end(), greater<string>());
string out;
for (auto& p : parts) out += p;
return out;
}Explanation
Think of a special binary string like balanced brackets: a 1 opens and a 0 closes. The whole string is made of several balanced pieces in a row, and we're allowed to reorder those pieces to make the largest result.
We scan with a running count, adding +1 for each 1 and -1 for each 0. Whenever count returns to 0, we've found one complete special chunk from index i to j.
Each chunk looks like 1 ... 0, where the inside is itself a smaller special string. So we recurse on that inside and rebuild the chunk as '1' + makeLargestSpecial(inside) + '0'. This makes every chunk internally as large as possible too.
Once we have all the chunks, we sort them in descending order and concatenate. Putting lexicographically larger pieces first gives the biggest overall string, since all pieces have balanced length and can be freely reordered.
Example: s = "11011000" splits into the chunks "1011000"... after recursing and sorting the inner pieces, the larger arrangement wins, producing "11100100".