Special Binary String - Solution & Explanation

Problem Overview: You’re given a binary string that is special: it contains the same number of 1s and 0s, and every prefix has at least as many 1s as 0s. You can swap adjacent special substrings. The goal is to rearrange the string to produce the lexicographically largest possible result.

Approach 1: Brute Force Rearrangement (Exponential Time, Exponential Space)

The naive idea is to generate all valid swaps of adjacent special substrings and track the lexicographically largest result. Each step tries every possible split where both sides remain valid special strings. This quickly explodes because the number of permutations grows exponentially with the number of segments. Time complexity is roughly O(2^n) in the worst case with large recursion trees, and space complexity is also O(2^n) due to storing generated states. This approach mainly helps understand the problem constraints but is not practical for large inputs.

Approach 2: Stack / Balanced Decomposition (O(n^2) time, O(n) space)

A special binary string behaves similarly to balanced parentheses. Iterate through the string while counting 1s and 0s. Whenever the counts match, you’ve found a minimal valid special substring. Extract these segments and store them. Each segment can then be processed recursively and combined back. While this decomposition is efficient, naive concatenation or repeated comparisons during reordering can push the time complexity toward O(n^2). This technique highlights the structural similarity between this problem and balanced structures often discussed in stack problems.

Approach 3: Recursive Decomposition and Sorting (O(n log n) time, O(n) space)

The optimal strategy recursively breaks the string into its smallest special components. Scan the string while maintaining a counter: increment for 1 and decrement for 0. When the counter returns to zero, you’ve identified a complete special substring. Recursively solve the inner portion s[i+1:j], wrap it with 1 and 0, and add the result to a list.

After extracting all components, sort them in descending lexicographic order and concatenate. Larger segments starting with more leading 1s produce bigger lexicographic values, so sorting ensures the globally optimal arrangement. The scan is linear and the sorting step dominates with O(k log k) where k is the number of segments, leading to overall O(n log n) time and O(n) recursion space.

This technique combines ideas from string manipulation and divide‑and‑conquer recursion. The recursive structure ensures every nested special substring is maximized before assembling the final answer.

Recommended for interviews: Recursive decomposition with sorting is the expected solution. It demonstrates recognition of the balanced structure, correct recursive segmentation, and greedy ordering for lexicographic maximization. Interviewers typically want to see how you detect valid segments and recursively optimize them using recursion.