761. Special Binary String (Hard)

https://leetcode.com/problems/special-binary-string/

Special binary strings are binary strings with the following two properties:

Given a special string S, a move consists of choosing two consecutive, non-empty, special substrings of S, and swapping them. (Two strings are consecutive if the last character of the first string is exactly one index before the first character of the second string.)

At the end of any number of moves, what is the lexicographically largest resulting string possible?

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.

Note:

1. S has length at most 50.
2. S is guaranteed to be a special binary string as defined above.

Solutions

class Solution {
    // Do not try this problem any more, too complicated

    public String makeLargestSpecial(String S) {
        int begin = 0;
        int count = 0;

        // to keep substrings of same number of 0 and 1
        List<String> ans = new ArrayList<>();

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

            if (count != 0) {
                continue;
            }

            // Reach here if the substring S.substring(begin, end+1) subject to count of 1 == count of 0

            // Technically, String.substring() prunes from index begin+1(inclusive) to end(exclusive)

            // Q. Why not include the chars at index begin and end?

            // Actually not only included, but also optimized silently. To make the outcome value the
            // maximum, the prefix should be 1 and the tail should be 0.

            // The underlying rule is that the head must carry different value from tail, which means
            // tail must be 0 if the head is 1 and the tail be 1 if the head is 0.

            // You can assume that the head and tail are both 1, such that the middle section
            // contains two more 0. Imagine the sequence is 1001, however, this sequence can be divided into to
            // sub sequences that satisfy above program logic, which means 1001 will never reach here.

            // Add the optimized substring, the special binary substrings are well organized of which
            // the larger one is placed in the front.

            ans.add('1' + makeLargestSpecial(S.substring(begin + 1, end)) + '0');

            // Proceed into a new execution and the end turns to be beginning
            begin = end + 1;
        }

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

        return String.join("", ans);
    }
}

Incorrect Solutions

References