Special Binary String

Problem

Balanced-packet encodings write a binary string that never dips below zero when read left to right (1s always at least 0s so far) and ends exactly at zero - a "special" string. The transmission protocol accepts any permutation produced by recursively rearranging balanced substrings. Given a special string, return the lexicographically largest special string you can produce.

Example 1:

Input: s = "10"
Output: "10"
Explanation: the minimal special string is already maximal - nothing to rearrange.

Example 2:

Input: s = "101100"
Output: "110010"
Explanation: parts are "10" and "1100"; sorting them descending gives "1100" + "10".

Example 3:

Input: s = "1101110000"
Output: "1111000100"
Explanation: a single nested part: strip the shell 1...0, maximize the inner "10111000" -> "11100010", re-enclose: "1" + "11100010" + "0".

Constraints:

• 1 <= s.length <= 50
• s consists of '0' and '1' only.
• s is a special string: every prefix has at least as many 1s as 0s, and the totals are equal.

Special-string shape (balance never negative, ends at 0):
 
s = 101100
      10        1100          <- two maximal balanced parts
      /\        /  \
     1  0      1    0
              (inner "10")
 
maximal each part: 10, 1100
descending concat: 1100 || 10 -> 110010

Solution Breakdown

Approach - decompose the string into maximal balanced parts, maximize each recursively, and sort the parts descending.

Scan with a running balance (+1 for 1, -1 for 0). Every position where the balance returns to zero closes one maximal balanced part - the string is a concatenation of such parts. Each part has a fixed shell: it begins with 1 (the balance would dip negative otherwise) and ends with 0 (the balance must return to zero), so a part spanning [i, j] is 1 + inner + 0 where inner = s[i+1:j]. The shell cannot move; the inner is itself a special string (its balance never dips below zero within the part and ends at zero before the closing 0), so maximizing the part means exactly one thing: recursively maximize the inner. The recursion bottoms out on empty or shell-only strings - 10 has empty inner and reproduces itself.

With every part independently maximal, one global decision remains: the order the parts concatenate in. Because the parts only interact through adjacency, the lexicographic maximum of the whole is achieved by placing the lexicographically greatest parts first - sort descending, concatenate. Swapping any adjacent pair into ascending order would replace a greater-leading prefix with a smaller one, strictly shrinking the result. Trace "101100": the balance zeroes at index 1 (part 10) and index 5 (part 1100); each maximizes to itself (1100's inner is 10, already maximal); sorted descending gives 1100 + 10 = "110010". Trace "1101110000": the balance first returns to zero only at the very end - one part 1 [10111000] 0; the inner maximizes to 11100010, so the answer is 1 + 11100010 + 0 = "1111000100".

Edge cases - "10" and other single-part strings with empty or maximal inners return themselves; repeated equal parts ("1010") sort to the same string, so the result equals the input when nothing can improve; a string that is already one maximal nested part never reorders parts at its top level - all its improvement comes from the recursion inside.

Complexity - O(n^2) worst case: each recursion level scans its substring and the slice copies it, with nesting depth up to n/2; the sort adds at most O(k log k) per level over k parts. O(n) space for the parts lists and recursion stack. The constraint bound (n <= 50) keeps this trivial; for large inputs an index-passing formulation avoids the slice copies.