DSA problem

Special Binary String

HardRecursionPattern: Recursiontop600GoogleFacebookAmazonCoursera

A special binary string is a binary string with the following two properties:

1. The number of 0s is equal to the number of 1s.
2. Every prefix of the binary string has at least as many 1s as 0s.

You are given a special binary string s. You can choose two consecutive non-empty special substrings of s and swap them. Two strings are consecutive if the last character of the first string is exactly one index before the first character of the second string. Return the lexicographically largest resulting string possible after applying the operation any number of times.

The key structural insight is that any special binary string can be uniquely decomposed into a concatenation of "top-level" special substrings, where each one starts at a balance of zero and returns to zero only at its end. Within each top-level substring, the outermost characters must be 1 (start) and 0 (end), so it has the form 1 + inner + 0 for some inner that is itself a special binary string.

The optimal recursive approach is therefore: split s into its top-level special substrings; for each piece, peel the outer 1 and 0 and recurse on the inner to make it lexicographically maximal; reassemble each piece as 1 + bestInner + 0; finally, sort all reassembled pieces in descending order and concatenate them. Sorting works because each piece is itself a valid special substring, and swapping consecutive special substrings is the only allowed move. The recursion terminates because every inner is strictly shorter than its parent.

Examples

Constraints

• 1 <= s.length <= 50
• s[i] is either '0' or '1'.
• s is a special binary string.

3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.

recursionstringgreedysorting

Browse all DSA problems