LeetCode 761 - Special Binary String

Difficulty: 🔴 Hard
Topics: String, Divide and Conquer, Sorting

Solution

Problem Understanding

The problem asks us to manipulate a special binary string to produce the lexicographically largest possible string. A special binary string has two properties: it contains equal numbers of 1s and 0s, and at every point in the string, the number of 1s is at least as many as the number of 0s. This is similar to well-formed parentheses, where 1 represents an opening parenthesis and 0 a closing parenthesis.

The input is a string s guaranteed to be a special binary string with a maximum length of 50 characters. The output should be the largest string you can form by repeatedly swapping consecutive special substrings.

Constraints tell us the input is relatively small, so recursive or divide-and-conquer solutions are feasible. The problem guarantees that the string is already special, so we don’t need to validate it.

Key edge cases include strings of length 2 (the smallest possible special string) and strings that are already the largest lexicographical form, which should remain unchanged.

Approaches

A brute-force approach would generate all possible sequences of consecutive special substrings and attempt every swap. This would eventually yield the largest string, but it is extremely inefficient because the number of valid swaps grows combinatorially with string length. Exploring all permutations explicitly is infeasible even for length 50.

The optimal approach relies on divide and conquer with recursion. The key insight is that every special binary string can be decomposed into smaller special substrings. Once you identify these top-level special substrings, you can recursively sort each of them in descending lexicographical order. By concatenating the sorted substrings, you achieve the largest possible string. This works because swaps of consecutive special substrings only affect their order, not the internal structure.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n!)	O(n!)	Generate all swaps of consecutive special substrings, extremely slow
Optimal	O(n^2)	O(n)	Divide and conquer by identifying and recursively sorting top-level special substrings

Algorithm Walkthrough

Initialize a count variable to track the balance of 1s and 0s and an empty list special_substrings to store the top-level special substrings.
Iterate over the string character by character. Increment count for 1 and decrement for 0.
When count returns to zero, the substring from the last start index to the current index is a top-level special substring.
For each top-level substring, remove the outer 1 and 0, recursively apply the algorithm to the inner substring, and then wrap it again with 1 and 0.
Collect all recursively processed substrings and sort them in descending lexicographical order.
Concatenate the sorted substrings and return the result.

Why it works: Each top-level special substring is independent in terms of possible swaps, so sorting them in descending order guarantees the lexicographically largest string. Recursion ensures that nested special substrings are also maximally ordered.

Python Solution

class Solution:
    def makeLargestSpecial(self, s: str) -> str:
        special_substrings = []
        count = 0
        start = 0
        for i, char in enumerate(s):
            count += 1 if char == '1' else -1
            if count == 0:
                inner = self.makeLargestSpecial(s[start + 1:i])
                special_substrings.append('1' + inner + '0')
                start = i + 1
        special_substrings.sort(reverse=True)
        return ''.join(special_substrings)

The Python solution iterates through s to identify top-level special substrings. For each, it recursively processes the inner substring, wraps it with 1 and 0, and then sorts all such substrings in reverse order to maximize the lexicographical value.

Go Solution

import "sort"

func makeLargestSpecial(s string) string {
    var specialSubstrings []string
    count, start := 0, 0
    for i, char := range s {
        if char == '1' {
            count++
        } else {
            count--
        }
        if count == 0 {
            inner := makeLargestSpecial(s[start+1 : i])
            specialSubstrings = append(specialSubstrings, "1"+inner+"0")
            start = i + 1
        }
    }
    sort.Slice(specialSubstrings, func(i, j int) bool {
        return specialSubstrings[i] > specialSubstrings[j]
    })
    result := ""
    for _, sub := range specialSubstrings {
        result += sub
    }
    return result
}

The Go solution mirrors the Python logic, using sort.Slice with a custom comparator to sort in descending order. Slice handling in Go replaces string slicing in Python, but the recursion and wrapping logic remains the same.

Worked Examples

Example 1: s = "11011000"

Step	Count	Substring Identified	Recursive Result
i=0	1	-	-
i=1	2	-	-
i=2	1	-	-
i=3	2	-	-
i=4	1	-	-
i=5	0	"11011000"	recursively sort "1010" → "10" + "10" → "11100100"

Example 2: s = "10"

Step	Count	Start	Substring Identified	Recursive Result
i=0	1	0	-	-
i=1	0	0	"10"	no inner, result "10"

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n^2)	Each substring may require slicing and concatenation, and sorting occurs at each recursion level. Worst case is quadratic.
Space	O(n)	Recursion depth and storage of substrings consume linear space.

Recursion is bounded by the depth of nested special substrings. Sorting at each level is linear in the number of top-level substrings, which is at most n/2.

Test Cases

# provided examples
assert Solution().makeLargestSpecial("11011000") == "11100100"  # Example 1
assert Solution().makeLargestSpecial("10") == "10"  # Example 2

# additional edge cases
assert Solution().makeLargestSpecial("111000") == "111000"  # already largest
assert Solution().makeLargestSpecial("110100") == "110100"  # nested minimal swap
assert Solution().makeLargestSpecial("1101101000") == "1110101000"  # more complex nesting
assert Solution().makeLargestSpecial("101010") == "101010"  # alternating 1s and 0s

Test	Why
"11011000"	Standard case with possible swaps
"10"	Minimal length
"111000"	Already largest form
"110100"	Nested structure, no change needed
"1101101000"	Nested and consecutive swaps needed
"101010"	No swaps possible, already maximal

Edge Cases

Minimal string length (2 characters): The smallest valid special string is "10". Any algorithm must handle it correctly without indexing errors. Both Python and Go solutions return it unchanged.
Already maximal string: Strings like "111000" do not require any swaps. Recursive sorting preserves the original string when it is already lexicographically largest.
Deeply nested special substrings: Strings such as "1101101000" have nested substrings that require recursive processing. Proper recursion ensures each nested level is maximally ordered before sorting top-level substrings. This handles the complexity introduced by multiple layers of special strings.