Skip to main content
Talentd

Special Binary String - Solution & Explanation

HardStringRecursion11 min readAsked at: Amazon, Microsoft, BNP Paribas +9
Practice this problem

Problem Statement

Special binary strings are binary strings with the following two properties:

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

You are given a special binary string s.

A move consists of choosing two consecutive, non-empty, special substrings of s, and swapping 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 mentioned operations on the string.

 

Example 1:

Input: s = "11011000"
Output: "11100100"
Explanation: The strings "10" [occuring at s[1]] and "1100" [at s[3]] are swapped.
This is the lexicographically largest string possible after some number of swaps.

Example 2:

Input: s = "10"
Output: "10"

 

Constraints:

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

Approach Overview

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.

Approach 1: Recursive Decomposition and Sorting

This approach leverages recursion to decompose the special binary string into smaller special substrings, sort these components, and then rebuild the string to achieve the lexicographically largest string. This works because by sorting the special substrings in descending order, larger lexicographical strings are formed.

The function recursively decomposes the string whenever a balance point is reached, i.e., when the count of '1's and '0's becomes zero. Once parts are decomposed, they are sorted in reverse (descending) order to achieve the lexicographically largest string.

Code

PythonJavaC++CC#JavaScript

Python

Java

C++

C

C#

JavaScript

Complexity

Time Complexity: O(n^2), where n is the length of the string, due to recursive decomposition and sorting.

Space Complexity: O(n), for storing the results and recursion stack.

Try this approach in the editor →

Approach 2: Recursion + Sorting

We can treat the special binary sequence as "valid parentheses", where 1 represents an opening parenthesis and 0 represents a closing parenthesis. For example, "11011000" can be viewed as "(()(()))".

Swapping two consecutive non-empty special substrings is equivalent to swapping two adjacent valid parentheses. We can use recursion to solve this problem.

We treat each "valid parenthesis" in string s as a part, process it recursively, and finally sort them to get the final answer.

The time complexity is O(n^2), and the space complexity is O(n), where n is the length of string s.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Recursive Decomposition and Sorting

Time Complexity: O(n^2), where n is the length of the string, due to recursive decomposition and sorting.

Space Complexity: O(n), for storing the results and recursion stack.

Recursion + Sorting—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force RearrangementO(2^n)O(2^n)Understanding the structure of valid special substrings; not practical for real constraints
Stack / Balanced DecompositionO(n^2)O(n)When identifying minimal balanced segments before optimization
Recursive Decomposition and SortingO(n log n)O(n)Optimal solution for interviews and production implementations

Video Solution

Special Binary String | Detailed Intuition | Dry Run | Leetcode 761 | codestorywithMIK • codestorywithMIK • 12,358 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Special Binary String easy or hard?
Special Binary String is classified as Hard on LeetCode. The difficulty comes from recognizing that the string behaves like balanced parentheses and that optimal results require recursively maximizing inner segments and sorting them for lexicographic order.
Special Binary String Python/Java solution
Most Python and Java implementations follow the same recursive pattern: scan the string while maintaining a balance counter, recursively process inner substrings, store results in a list, sort the list in descending order, and join them. This keeps the time complexity around O(n log n) with O(n) extra space.
How to solve Special Binary String in O(n)?
A strictly O(n) algorithm is difficult because the optimal solution requires sorting special substrings to maximize lexicographic order. Most accepted implementations run in O(n log n) time due to the sorting step. The linear part of the algorithm comes from scanning the string and recursively decomposing balanced segments.
What is the best approach for Special Binary String?
Recursive decomposition with lexicographic sorting is the most effective approach. The algorithm splits the string into minimal special substrings using a balance counter, recursively maximizes each inner substring, then sorts the results in descending order before concatenation. This guarantees the largest possible lexicographic string.
Is Special Binary String asked at Google/Amazon/Meta?
Special Binary String is considered a hard-level string and recursion problem and has appeared in advanced interview preparation sets. Variants involving balanced structures, recursion, and lexicographic maximization are common at companies like Google, Amazon, and Meta.
What data structure is used in Special Binary String?
The solution mainly relies on recursion and dynamic substring construction. A list or array is used to store extracted special substrings before sorting them. Conceptually, the problem is similar to balanced parentheses problems often solved with stacks.
What is the time complexity of Special Binary String?
The optimal recursive decomposition approach runs in O(n log n) time. Scanning the string to detect special substrings takes O(n), while sorting the extracted components dominates with O(k log k), where k is the number of segments. Space complexity is O(n) due to recursion and substring storage.

Ready to solve this problem?

Practice Special Binary String with our built-in code editor and test cases.

Practice on FleetCode
Previous

Number of Good Binary Strings

Next

Valid Parenthesis String