Special Binary String

Problem Statement

A special binary string is structured to maintain an equal number of 0s and 1s, with every prefix having as many 1s as 0s or more. Given such a binary string s, you are permitted to execute operations where two consecutive, non-empty, and valid special substrings within s can be swapped. This particular swapping operation needs the first string to end right before the second one begins.

Your task is to determine the lexicographically largest string possible from s through any number of these swap operations.

Examples

Example 1

Input:

s = "11011000"

Output:

"11100100"

Explanation:

The strings "10" [occuring at s[1]] and "1100" [at s[3]] are swapped.
This is the lexicographically largest string possible after some number of swaps.

Example 2

Input:

s = "10"

Output:

"10"

Constraints

• 1 <= s.length <= 50
• s[i] is either '0' or '1'.
• s is a special binary string.

Approach and Intuition

Understanding how swapping affects the lexicographical ordering of the string is critical. In the construction of the largest possible string lexicographically from a special binary string, consider the following intuition along with deductive steps:

1. Identify all substrings that qualify independently as special binary strings. Start by maintaining a balance count with an initial value of zero and iterate through the string:

   • Increment the balance for every 1 encountered and decrement for every 0.
   • Whenever the balance returns to zero, it indicates a valid special substring.

2. With identified special substrings, consider their order:

   • A higher concentration of 1s at the start of any substring or the entire string will inherently make the string larger in lexicographical terms.

3. Sort these substrings in descending order where possible:

   • When placed consecutively, substrings starting with '1' and leading with as many sequential '1's as possible, should be positioned before others.

4. Strategically concatenate:

   • Reassemble these substrings back into the main string ensuring that the sequence adheres to the descending lexicographical order determined in the earlier step.

This approach focuses on reordering the whole substrings rather than moving individual characters, respecting the defined rules of special binary strings and operations allowed.

Solutions

class Solution {
    public String createMaximumSpecialSequence(String input) {
        if (input.isEmpty()) return input;
        int startIndex = 0, balance = 0;
        List<String> specialSegments = new ArrayList<>();
        for (int index = 0; index < input.length(); index++) {
            balance += input.charAt(index) == '1' ? 1 : -1;
            if (balance == 0) {
                specialSegments.add("1" + createMaximumSpecialSequence(input.substring(startIndex+1, index)) + "0");
                startIndex = index + 1;
            }
        }
        Collections.sort(specialSegments, Collections.reverseOrder());
        StringBuilder result = new StringBuilder();
        for (String segment: specialSegments)
            result.append(segment);
        return result.toString();
    }
}