Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Treat 1 as an opening parenthesis and 0 as a closing one. Each return of the balance to zero ends a smallest top-level special block. Such a block is 1 + inner + 0, where inner is itself special. Adjacent top-level blocks can be swapped freely, and the same reasoning applies recursively inside each block.

Approach

Scan the string, increasing the balance for 1 and decreasing it for 0.
Whenever the balance returns to zero, recursively maximize the block's interior, then restore its surrounding 1 and 0.
Sort the resulting top-level blocks in descending lexicographical order and concatenate them. Their primitive structure prevents one distinct block from being a prefix of another, so this order maximizes their concatenation.
An empty interior returns an empty string. Optimizing interiors first and ordering the independent sibling blocks at every level produces the largest reachable special string.

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

            for r in range(len(s)):
                bal = bal + 1 if s[r] == '1' else bal - 1
                if bal == 0:
                    next = dfs(s[l + 1: r])
                    res.append('1' + next + '0')
                    l = r + 1

            res.sort(reverse = True)
            return "".join(res)

        return dfs(s)

Complexity analysis

Let n = s.length. Recursive slicing/string construction can copy O(n²) characters. Across recursion levels, comparison-based sorting of canonicalized blocks adds a safe O(log n) factor, so worst-case time is O(n² log n). Auxiliary space is O(n²) across nested substrings/results, with O(n) final output.