Problem Statement in English

You’re given a special binary string. A special binary string is a binary string with the following two properties:

  1. The number of 0’s is equal to the number of 1’s.
  2. Every prefix of the binary string has at least as many 1’s as 0’s.

Return the lexicographically largest special binary string that can be obtained by performing the following operation any number of times:

Approach

There’s a couple really important observations to make here that help us solve the problem:

  • Every special binary string can be represented as "1" + A + "0" + B, where A and B are also special binary strings. This is because the first character must be a "1" and the last character must be a "0". The substring between the first "1" and the last "0" must also be a special binary string, and the substring after the last "0" must also be a special binary string.

    • This has the added implication that we can recursively break down the string into smaller special binary strings and sort them to get the lexicographically largest string.

    • Also, since a special binary string must start with a "1" and end with a "0", once we optimise a certain substring we can be sure that we can set it aside and only need to process the rest of the string. The optimised string will not need or be part of any further optimisations.

  • We can sort the special binary strings in decreasing order to get the lexicographically largest string. This is because we can swap any two consecutive special binary strings to get a larger string.

Solution in Python


class Solution:
    def makeLargestSpecial(self, s: str) -> str:
        res = []

        i = 0
        count = 0

        for j, c in enumerate(s):
            if c == "1":
                count += 1
            else:
                count -= 1

            if count == 0:
                middle = self.makeLargestSpecial(s[i + 1 : j])
                res.append("1" + middle + "0")
                i = j + 1

        res.sort(reverse=True)

        return "".join(res)

Complexity

  • Time: $O(n^2)$
    Since we recursively break down the string into smaller special binary strings and sort them. The sorting step takes $O(nlog(n))$ time, and we do this for each substring, which can lead to a worst-case time complexity of $O(n^2)$.

  • Space: $O(n)$
    Since we store the result in a list and then join it to get the final string.

Mistakes I Made

I had to look this one up

And we are done.