Special Binary String

Make Largest Special

Difficulty: Hard

Category: Recursion, Sorting

Problem Statement

A binary string is considered special if it meets the following criteria:

• It is comprised of '1's and '0's.
• The count of '1's is equal to the count of '0's.
• For any prefix of the string, the count of '1's is greater than or equal to the count of '0's.

You are given a special string s. Your task is to make the largest lexicographical special string possible by applying the following operations any number of times:

• Split s into multiple special substrings.
• Sort the substrings in descending lexicographical order.
• Join the sorted substrings back together.

Return the largest special string.

Examples

Example 1

Input: s = "11011000"

Output: "11100100"

Explanation: Split the string into special substrings: ["1100", "10"]. Sort them in descending order: ["1110", "00"]. Join them to form the result: "11100100".

Algorithm Explanation

The problem relies on identifying "special substrings" and recursively restructuring them to form the largest lexicographical order. Here's how the algorithm works:

1. Iterate through the string while maintaining a balance count of '1's and '0's.
2. Whenever count becomes 0, it indicates the end of a special substring.
3. Extract the substring and process its "inner part" recursively, excluding the outermost '1' and '0'.
4. Reconstruct the substring by adding the outer '1' and '0' around the result of the recursive call.
5. Sort all the substrings in descending order.
6. Concatenate the sorted substrings to form the result.

Code Implementation

Java

public String makeLargestSpecial(String s) {
    if (s.length() <= 2) return s; // Base case: smallest special string

    List substrings = new ArrayList<>();
    int count = 0, start = 0;

    // Split the string into special substrings
    for (int i = 0; i < s.length(); i++) {
        count += s.charAt(i) == '1' ? 1 : -1; // Update count for '1' or '0'
        if (count == 0) { // Found a complete special substring
            // Take the full substring including "1" and "0"
            String specialSubstring = s.substring(start, i + 1);
            // Process inner substring recursively, excluding the outermost "1" and "0"
            String inner = makeLargestSpecial(specialSubstring.substring(1, specialSubstring.length() - 1));
            substrings.add("1" + inner + "0"); // Reconstruct the special substring
            start = i + 1; // Move to the next substring
        }
    }

    // Sort substrings in descending order
    Collections.sort(substrings, Collections.reverseOrder());

    // Concatenate substrings to form the largest special string
    return String.join("", substrings);
}

        

Python

def makeLargestSpecial(s: str) -> str:
    if len(s) <= 2:
        return s  # Base case: smallest special string

    substrings = []
    count = 0
    start = 0

    # Split the string into special substrings
    for i, char in enumerate(s):
        count += 1 if char == '1' else -1
        if count == 0:
            # Take the full substring including "1" and "0"
            special_substring = s[start + 1:i]
            # Process inner substring recursively
            inner = makeLargestSpecial(special_substring)
            substrings.append(f"1{inner}0")
            start = i + 1

    # Sort substrings in descending order
    substrings.sort(reverse=True)

    # Concatenate substrings to form the largest special string
    return ''.join(substrings)

        

C++

class Solution {
public:
    string makeLargestSpecial(string s) {
        if (s.size() <= 2) return s; // Base case: smallest special string

        vector substrings;
        int count = 0, start = 0;

        // Split the string into special substrings
        for (int i = 0; i < s.size(); ++i) {
            count += s[i] == '1' ? 1 : -1;
            if (count == 0) {
                // Take the full substring including "1" and "0"
                string specialSubstring = s.substr(start + 1, i - start - 1);
                // Process inner substring recursively
                string inner = makeLargestSpecial(specialSubstring);
                substrings.push_back("1" + inner + "0");
                start = i + 1;
            }
        }

        // Sort substrings in descending order
        sort(substrings.rbegin(), substrings.rend());

        // Concatenate substrings to form the largest special string
        return accumulate(substrings.begin(), substrings.end(), string());
    }
};