761. Special Binary String

/**
 * Problem: LeetCode 761 - Special Binary String
 * Difficulty: Hard
 * Language: Java
 * Author: CodeByTushu
 */
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    public String makeLargestSpecial(String s) {
        if (s.length() <= 2) {
            return s;
        }

        List<String> list = new ArrayList<>();
        int count = 0;
        int start = 0;

        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '1') {
                count++;
            } else {
                count--;
            }

            if (count == 0) {
                // Primitive special substring found: s[start ... i]
                // The inner substring is s[start + 1 ... i - 1]
                String inner = makeLargestSpecial(s.substring(start + 1, i));
                list.add("1" + inner + "0");
                start = i + 1;
            }
        }

        Collections.sort(list, Collections.reverseOrder());

        StringBuilder sb = new StringBuilder();
        for (String sub : list) {
            sb.append(sub);
        }

        return sb.toString();
    }
}

"""
Problem: LeetCode 761 - Special Binary String
Difficulty: Hard
Language: Python
Author: CodeByTushu
"""
class Solution:
    def makeLargestSpecial(self, s: str) -> str:
        if len(s) <= 2:
            return s

        count = 0
        start = 0
        parts = []

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

            if count == 0:
                inner = self.makeLargestSpecial(s[start + 1:i])
                parts.append("1" + inner + "0")
                start = i + 1

        parts.sort(reverse=True)
        return "".join(parts)

/**
 * Problem: LeetCode 761 - Special Binary String
 * Difficulty: Hard
 * Language: C++
 * Author: CodeByTushu
 */
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    string makeLargestSpecial(string s) {
        if (s.length() <= 2) {
            return s;
        }

        vector<string> parts;
        int count = 0;
        int start = 0;

        for (int i = 0; i < (int)s.length(); i++) {
            if (s[i] == '1') {
                count++;
            } else {
                count--;
            }

            if (count == 0) {
                string inner = makeLargestSpecial(s.substr(start + 1, i - start - 1));
                parts.push_back("1" + inner + "0");
                start = i + 1;
            }
        }

        sort(parts.begin(), parts.end(), greater<string>());

        string result = "";
        for (const string& part : parts) {
            result += part;
        }

        return result;
    }
};

/**
 * Problem: LeetCode 761 - Special Binary String
 * Difficulty: Hard
 * Language: JavaScript
 * Author: CodeByTushu
 */
/**
 * @param {string} s
 * @return {string}
 */
var makeLargestSpecial = function(s) {
    if (s.length <= 2) {
        return s;
    }

    const parts = [];
    let count = 0;
    let start = 0;

    for (let i = 0; i < s.length; i++) {
        if (s[i] === '1') {
            count++;
        } else {
            count--;
        }

        if (count === 0) {
            const inner = makeLargestSpecial(s.substring(start + 1, i));
            parts.push("1" + inner + "0");
            start = i + 1;
        }
    }

    parts.sort((a, b) => b.localeCompare(a));
    return parts.join("");
};