Special Binary String
Understanding the Problem
A special binary string has two properties: equal counts of 1s and 0s, and every prefix has at least as many 1s as 0s. This maps directly onto balanced parentheses. Replace every 1 with ( and every 0 with ), and a special binary string becomes a valid balanced parentheses string. The prefix constraint is what prevents an unmatched closing bracket from appearing before its opener.
So "11011000" maps to "(()(()))". Like balanced parentheses, special binary strings have a recursive structure: the string decomposes into top-level groups, and the interior of each group is itself a special binary string. The problem asks us to rearrange these groups through adjacent swaps to produce the lexicographically largest result. Since 1 > 0, we want the 1s as early as possible.
This leaves two questions: what is the optimal arrangement of the top-level groups, and how do we handle the nested structure inside each group?
Key Constraints:
1 <= s.length <= 50→ The string is small, so even an exponential arrangement search over the top-level groups runs in time. A polynomial solution leaves a wide margin.sis guaranteed to be a special binary string → The input needs no validation, and the recursive decomposition always produces valid sub-problems.
Approach 1: Brute Force (Try All Permutations)
Intuition
Identify all the top-level special substrings and try every possible ordering. Swapping adjacent special substrings any number of times lets us produce any permutation of those substrings, since any permutation can be reached through a sequence of adjacent transpositions. So we generate all permutations, concatenate each one, and keep the lexicographically largest.
Each top-level special substring can contain nested special substrings inside it. A complete brute force has to recursively try rearranging the nested substrings at every level too. The number of arrangements grows factorially, but with n up to 50 the number of top-level substrings at any single level stays small enough to enumerate.
Algorithm
- Scan through the string, tracking a running balance (add 1 for each '1', subtract 1 for each '0'). Each time the balance returns to 0, mark the boundary of a top-level special substring.
- For each top-level special substring, strip the outer '1' and '0', and recursively apply the same process to the interior.
- At each recursion level, generate all permutations of the top-level pieces.
- For each permutation, concatenate the pieces and track the lexicographically largest result.
- Return the largest result found.
Example Walkthrough
Code
- Time Complexity: O(n * k!), where k is the number of top-level groups at a level. We generate all k! permutations, and concatenating each one touches strings of total length up to n. With n at most 50, k stays small in practice.
- Space Complexity: O(n * k!). We materialize all k! permutation strings of total length n. The recursion can nest up to n/2 levels deep, adding O(n) stack space.
Generating every permutation is wasteful when we only need the largest one. The next approach replaces the permutation search with a single sort.
Approach 2: Recursive Decomposition with Sorting (Optimal)
Intuition
A special binary string decomposes into top-level groups, the same way balanced parentheses do. Each top-level group starts with a 1, ends with a 0, and everything in between is itself a special binary string.
For "11011000", scanning and tracking the balance (increment for 1, decrement for 0) brings the balance back to 0 only at the last character, so the entire string is one top-level group. Strip the outer 1 and 0 and the interior is "101100", which decomposes into two top-level groups: "10" and "1100".
Because adjacent special substrings can be swapped any number of times, the top-level groups can be reordered into any arrangement. Sorting them in descending order produces the largest concatenation. Before sorting, we recursively optimize the interior of each group, so the comparison ranks groups that are already in their best internal form.
The ordering matters: a group's interior must be optimized first, because rearranging the outer groups cannot fix a sub-optimal interior. The outer 1 and 0 of a group never move relative to each other, so each group's internal layout is fixed by its own recursion, and only the sequence of whole groups is free to change.
One detail needs justification: why does sorting the groups in descending order maximize the concatenation? Every top-level group has equal numbers of 1s and 0s and starts with a 1, so no group is a prefix of another. When neither of two strings is a prefix of the other, their first differing character decides both the lexicographic comparison of the strings themselves and the comparison of the two concatenation orders. So putting the lexicographically larger group first is always at least as good, and a comparison sort that places each pair in that order yields the global maximum.
The swap operation is what makes any ordering reachable: adjacent transpositions can compose into any permutation of the groups, so no arrangement is off-limits.
Algorithm
- If the string is empty or has length 2, return it as-is (base case).
- Initialize a balance counter to 0 and a start pointer to 0.
- Scan through the string character by character. Add 1 to balance for each '1', subtract 1 for each '0'.
- Each time balance returns to 0, extract the top-level special substring from start to the current position.
- Strip the outer '1' and '0', recursively call the function on the interior.
- Store the result as "1" + recursive result + "0".
- After scanning the entire string, sort all collected pieces in descending lexicographic order.
- Concatenate and return.
Example Walkthrough
Code
- Time Complexity: O(n^2). At each recursion level, we scan through all characters to find top-level groups (O(n)). The recursion depth is at most n/2. Total work across all levels is O(n * n/2) = O(n^2).
- Space Complexity: O(n^2). The recursion stack can go O(n/2) deep, and at each level we create strings of total length proportional to n.