Problem statement

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

Solution

We can notice that special binary string is actually correct brackets expression and what we allowed to do is to change places of two adjacent group of brackets on the same level. Let us iterate through our string and find the external layer of brackets: all places, where balance is equal to 0. Then we apply recursively our function for each inside of brackets, and sort it in reverse order: we need to have lexicographically largest string.

Complexity

Worst time complexity is O(n^2*log n). I think this estimate can be improved to O(n^2), because each time sum of lengths of sorted strings is not so big. Space complexity is O(n).

Code

class Solution:
    def makeLargestSpecial(self, S):
        balance, split = 0, []
        for i in S:
            if balance == 0: split.append("")
            split[-1] += i
            balance += (i=="1")*2 - 1
           
        res = ["1" + self.makeLargestSpecial(p[1:-1]) + "0" for p in split]
        return "".join(sorted(res)[::-1])