Abstract / Summary

A special binary string can be split into equal numbers of zeros and ones followed by more special binary strings.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 61% (20k+ submissions).

Typical patterns to solve this problem:

• Recursion
• String

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a recursive solution for constructing the lexicographically largest “special” binary string. A special string is defined by two properties: it starts with a '1', ends with a '0', and every prefix contains at least as many '1' characters as '0' characters, with the total counts equal. The algorithm decomposes the input into its top-level special components, recursively processes the interior of each component, and finally reassembles the parts in descending lexical order to achieve the maximal result.

Key Steps

The entry point checks for an empty input, which is a valid special string and is returned unchanged.

if not s:
    return s

The core of the algorithm iterates over the characters while maintaining a balance counter (special). The counter increments for '1' and decrements for '0'. When the counter returns to zero, a complete top-level special segment has been identified.

parts   = []
left    = 0
special = 0
for right, c in enumerate(s):
    special += +1 if c == "1" else -1
    if special == 0:
        deeper = self.makeLargestSpecial(s[left + 1 : right])
        parts.append("1" + deeper + "0")
        left   = right + 1

Inside the loop, the substring between left + 1 and right represents the interior of the current special segment (the part between the outermost '1' and '0'). The method calls itself recursively to transform this interior into its largest possible form. The result is then wrapped with the surrounding '1' and '0' and stored in the parts collection.

After the entire string has been partitioned, the collected parts are sorted in reverse lexical order. This ordering guarantees that concatenating them yields the overall largest special string.

return "".join(sorted(parts, reverse = True))

Edge Cases Handled

The algorithm explicitly handles the case of an empty string, returning it directly without further processing. Because the loop relies on the balance counter reaching zero, any input that does not conform to the special-string definition (for example, an unmatched number of '1' and '0' characters) would never produce a zero balance and thus would result in an empty parts list. In such a scenario, the final join operation returns an empty string, which aligns with the definition that an empty string is considered special.

When the input consists of a single top-level special segment, the recursion processes the interior substring, which may itself be empty. The recursive call on an empty substring returns an empty string, and the outer call reconstructs the segment as "1" + "" + "0" yielding "10", the correct largest form for that minimal case.

Nested special structures are naturally accommodated because each identified segment triggers a recursive call on its interior. This recursion continues until the innermost level, which may be empty, ensuring that all levels of nesting are transformed appropriately before the outermost concatenation.

Performance Optimizations

The solution avoids constructing intermediate strings repeatedly by slicing only the interior portion of each segment (s[left + 1 : right]). This slice operation creates a new string of exactly the needed length, preventing unnecessary copying of characters outside the current segment.

Sorting is performed only on the list of top-level parts rather than on the entire string. Because the number of top-level parts is bounded by the number of '1' characters at the outermost level, the sorting work is limited to a relatively small collection, which reduces overhead compared to a naïve approach that might sort many smaller fragments.

Recursive calls are made on strictly smaller substrings, guaranteeing that each character participates in at most one recursive level of processing. This property eliminates redundant work and ensures that the total amount of work scales proportionally with the size of the input.

The use of a single pass to both identify segment boundaries and accumulate the parts list eliminates the need for a secondary traversal, consolidating detection and collection into one efficient loop.

Imagine you have a long string of ones and zeros. Think of this string like a row of building blocks where every one is a little starting door and every zero is a little closing door. The goal is to rearrange these blocks to make the coolest, biggest shape possible.

To do this, the code acts like a detective searching for tiny matched sets. It looks through the row and keeps count. Every time it finds a one, it adds one to the count, and every time it finds a zero, it takes one away. When the count hits zero again, it means a perfect group of blocks has been found where every door has a partner.

Once a group is found, it is taken out and sent through the same process again to see if there are even smaller groups hidden inside. It keeps breaking things down until everything is perfectly organized.

After all those little groups are tucked away, the blocks are put back together. The secret to making the biggest arrangement is to put the best, largest pieces at the front of the line. By sorting all those pieces from biggest to smallest and joining them back up, the final row of blocks becomes the most impressive one you can make.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

not analyzed yet

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++			Java			Python	TS
	WalkCCC	C++			Java			Python
	leetcode.ca	C++			Java		Go	Python	TS
	LeetcodeHelp	C++			Java			Python
	Progiez	C++			Java			Python
github	black-shadows	C++
	charles-wangkai				Java
	everthis		JS
	JoshCrozier		JS
	ruoru			Rust
	suxrobGM					C#
	wisdompeak	C++
	withaarzoo	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
JoshCrozier	JavaScript
ruoru	Rust
suxrobGM	C#
wisdompeak	C++
withaarzoo	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality