Special Binary String

A special binary string has equal numbers of 1 and 0, and every prefix has at least as many 1s as 0s. Scan with a balance counter: add one for 1, subtract one for 0. Whenever balance returns to zero, you found a primitive block of the form 1 + inner + 0. Recursively maximize inner, rebuild that block, and collect it. The complete primitive blocks can be reordered without breaking validity, so sort them in descending lexicographic order and concatenate. Putting the lexicographically largest valid block earliest gives the maximum result, while recursion ensures each block is itself maximal. Avoid sorting individual characters, which destroys the prefix property. If there are n characters, recursive parsing is linear apart from sorting sibling blocks; conservative complexity is O(n^2 log n) in heavy string-copying implementations, with O(n) stack/output space. Discuss substring handling if performance matters.