🧬 Beginner-Friendly Guide 'Special Binary String' - Problem 761 (C++, Python, JavaScript)

#programming #cpp #javascript #python

Navigating complex string manipulations can feel like untangling a knot, but "Special Binary Strings" follow a hidden, logical pattern. This problem is a classic example of how treating strings like nested structures, similar to balanced parentheses, can simplify a seemingly "Hard" difficulty challenge into a manageable recursive strategy.

Problem Summary

You're given:
A special binary string where the total number of 0s equals the total number of 1s, and every prefix contains at least as many 1s as 0s.

Your goal:
Swap any two consecutive, non-empty special substrings to create the lexicographically largest version of the string possible.

Intuition

To solve this, it helps to think of the string not as bits, but as balanced parentheses. If "1" is an opening bracket "(" and "0" is a closing bracket ")", a "Special Binary String" is essentially a valid mathematical grouping.

Because we can swap consecutive special substrings, our objective is to move the "heavier" substrings (those starting with more 1s) to the front. The core logic follows these steps:

Split: Break the string into its smallest possible "Special" components. A component is finished whenever the count of 1s and 0s balances out to zero.
Recurse: Each component itself consists of a "1" at the start, a "0" at the end, and another special string inside. We must recursively call our function on that inner part to ensure it is also as large as possible.
Sort: Once we have all our optimized components, we sort them in descending order. This ensures the largest values appear first lexicographically.
Join: Concatenate the sorted strings back together.

Walkthrough: Understanding the Examples

Input:

Identify Substrings: We track the balance.
(count: 1)
(not yet balanced)
(balance hits 0 at the very end).
Wait, the whole string is one special block! We look inside the outer "1" and "0".
Inner Processing: Inside the first and last characters of , we find .
This splits into and .
Recursion and Sorting:
Substrings are "10" and "1100".
Sorting them in descending order gives "1100" followed by "10".
Reassemble: Put the outer "1" and "0" back around the sorted inner parts if necessary, or swap the identified consecutive special substrings. In the example swap: becomes , resulting in .

Code Blocks

C++

class Solution {
public:
    string makeLargestSpecial(string s) {
        if (s.empty()) return "";

        vector<string> substrings;
        int balance = 0;
        int start = 0;

        for (int i = 0; i < s.length(); ++i) {
            balance += (s[i] == '1' ? 1 : -1);

            if (balance == 0) {
                // Remove the outer 1 and 0, recurse, then wrap them back
                substrings.push_back("1" + makeLargestSpecial(s.substr(start + 1, i - start - 1)) + "0");
                start = i + 1;
            }
        }

        // Sort substrings lexicographically in descending order
        sort(substrings.begin(), substrings.end(), greater<string>());

        string result = "";
        for (const string& sub : substrings) {
            result += sub;
        }

        return result;
    }
};

Python

class Solution:
    def makeLargestSpecial(self, s: str) -> str:
        if not s:
            return ""

        substrings = []
        balance = 0
        start = 0

        for i, char in enumerate(s):
            balance += 1 if char == '1' else -1

            if balance == 0:
                # Recurse on the inner string and wrap with 1...0
                inner = s[start + 1 : i]
                substrings.append("1" + self.makeLargestSpecial(inner) + "0")
                start = i + 1

        # Sort descending to get the lexicographically largest result
        substrings.sort(reverse=True)
        return "".join(substrings)

JavaScript

/**
 * @param {string} s
 * @return {string}
 */
var makeLargestSpecial = function(s) {
    if (s.length === 0) return "";

    let substrings = [];
    let balance = 0;
    let start = 0;

    for (let i = 0; i < s.length; i++) {
        balance += (s[i] === '1' ? 1 : -1);

        if (balance === 0) {
            // Extract the middle part, recurse, and add back the framing bits
            let inner = s.substring(start + 1, i);
            substrings.push("1" + makeLargestSpecial(inner) + "0");
            start = i + 1;
        }
    }

    // Sort descending and join
    return substrings.sort((a, b) => b.localeCompare(a)).join('');
};

Key Takeaways

Recursion on Nested Structures: Recognizing that "Special Strings" behave like nested brackets allows us to solve the problem by solving the smallest sub-problems first.
Greedy Sorting: To achieve the "lexicographically largest" result, the best strategy is often to sort components in descending order.
Balance Tracking: Using a simple integer counter (increment for '1', decrement for '0') is an efficient way to identify boundaries in balanced string problems.

Final Thoughts

This problem is a fantastic exercise in structural decomposition. While it appears in the "Hard" category, the logic mirrors how compilers parse code or how data is structured in XML and JSON. In real-world software engineering, being able to identify these recursive patterns is vital for building search engines, data parsers, or even file systems. Mastering this will sharpen your ability to handle hierarchical data in any language.

DEV Community