Approach #1: Recursion [Accepted]

Intuition

We can represent binary strings as "up and down" drawings, as follows:

In such a drawing, "1" is a line up one unit, and "0" is a line down one unit, where all lines are 45 degrees from horizontal.

Then, a binary string is special if and only if its up and down drawing does not cross below the starting horizontal line.

Now, say a special binary string is a mountain if it has no special proper prefix. When viewed through the lens of up and down drawings, a special binary string is a mountain if it touches the starting horizontal line only at the very beginning and the very end of the drawing. Notice that every special string can be written as consecutive mountains.

Without loss of generality, we can assume we only swap mountains. Because if we swap special adjacent substrings A and B, and A has mountain decomposition , then we could instead swap and , then and , and so on.

Also, if has mountain decomposition , and we choose to start not at the start of some , then has global height , and so cannot be special if it includes parts of another mountain as the end of mountain will cause it to dip to global height .

Algorithm

Say F(String S) is the desired makeLargestSpecial function. If S has mountain decomposition , the answer is , as swaps A, B involving multiple cannot have A or B start differently from where these start.

It remains to determine how to handle the case when is a mountain. In that case, it must start with "1" and end with "0", so the answer is "1" + F([S[1], S[2], ..., S[N-2]]) + "0".

Complexity Analysis

  • Time Complexity: , where is the length of .

  • Space Complexity: .


Analysis written by: @awice.