LeetCode 761: Special Binary String — Recursive Decomposition & Custom Sort Proof

Problem: LeetCode 761 — Special Binary String

Platform: LeetCode | Problem Number: 761

A special binary string satisfies two properties:

The number of 0 equals the number of 1.

Every prefix has at least as many 1 s as 0 s.

Given a special binary string S, an operation swaps two adjacent, non-empty special substrings. After any number of operations, what is the lexicographically largest possible result?

Example: Input: "11011000" → Output: "11100100" (swap "10" at index 1 with "1100" at index 3).

Solution Approach

Score Definition and Decomposition

Assign each character a score: 1 = +1, 0 = -1. By definition, the total score of S is 0, and no prefix has a negative score.

Decompose S into minimal special substrings called item s (each cannot be split further). Every item has total score 0.

Proof: Every Minimal item Has Form 1...0

By contradiction: an item has total score 0 and non-zero length, so it contains both 1 and 0.

If the first character were 0, the prefix starting at that character would have negative score, violating the special-string property.

If the last character were 1, removing it would leave a negative score, again violating the property.

Hence every minimal item must start with 1 and end with 0.

Two-Step Construction

Internal reorder: For each item (which is 1 + middle + 0), recursively apply the same process to the middle substring to maximize its lexicographical order.

External reorder: Sort the resulting item s among themselves to maximize the overall concatenation.

Because the problem imposes no constraints on the final string beyond being a permutation of the original item s, the two steps are independent.

Custom Sorting Logic and Total Order Proof

To order two item s a and b, compare the concatenations ab and ba lexicographically. Define: a@b if a must precede b (i.e., ab > ba). b@a if b must precede a (i.e., ba > ab). a#b if they are equivalent (i.e., ab = ba).

We prove this comparator induces a total order (i.e., it is a valid sorting criterion) by verifying three properties:

Completeness

For any two items a and b, the strings ab and ba are equal in length. Lexicographical order on equal-length strings is a total order, so exactly one of a@b, b@a, or a#b holds.

Antisymmetry

If a@b and b@a both held, then ab > ba and ba > ab, impossible. Hence a@b and b@a imply a#b.

Transitivity

Assume a@b and b@c. We must show a@c (i.e., ac > ca). Because ab, ba, bc, cb, ac, ca are all equal-length, lexicographical comparison reduces to numeric comparison of the binary strings. The proof considers the three possible relations between a and c ( a@c, c@a, a#c) and shows that only a@c is consistent with a@b and b@c. The argument relies on the fact that the custom comparator's decision depends only on the first differing character between the two concatenated strings.

The article includes visual proofs for the three transitivity cases:

Thus the comparator is transitive, completing the total-order proof. Sorting the item s with this comparator yields the lexicographically largest arrangement.

Code Implementations

Java

class Solution {
    public String makeLargestSpecial(String s) {
        if (s.length() == 0) return s;
        List<String> list = new ArrayList<>();
        char[] cs = s.toCharArray();
        for (int i = 0, j = 0, k = 0; i < cs.length; i++) {
            k += cs[i] == '1' ? 1 : -1;
            if (k == 0) {
                list.add("1" + makeLargestSpecial(s.substring(j + 1, i)) + "0");
                j = i + 1;
            }
        }
        Collections.sort(list, (a, b) -> (b + a).compareTo(a + b));
        StringBuilder sb = new StringBuilder();
        for (String str : list) sb.append(str);
        return sb.toString();
    }
}

C++

class Solution {
public:
    string makeLargestSpecial(string s) {
        if (s.empty()) return s;
        vector<string> list;
        for (int i = 0, j = 0, k = 0; i < s.length(); i++) {
            k += s[i] == '1' ? 1 : -1;
            if (k == 0) {
                list.push_back("1" + makeLargestSpecial(s.substr(j + 1, i - j - 1)) + "0");
                j = i + 1;
            }
        }
        sort(list.begin(), list.end(), [](const string &a, const string &b) {
            return (b + a).compare(a + b) < 0;
        });
        string result;
        for (const string &str : list) result += str;
        return result;
    }
};

TypeScript

function makeLargestSpecial(s: string): string {
    const list = new Array<string>();
    for (let i = 0, j = 0, k = 0; i < s.length; i++) {
        k += s[i] == '1' ? 1 : -1;
        if (k == 0) {
            list.push('1' + makeLargestSpecial(s.substring(j + 1, i)) + '0');
            j = i + 1;
        }
    }
    list.sort((a, b) => (b + a).localeCompare(a + b));
    return [...list].join("");
}

Time Complexity: O(n log n) due to sorting, where n is the string length.

Space Complexity: O(n) for recursion stack and substring storage.