This approach leverages recursion to decompose the special binary string into smaller special substrings, sort these components, and then rebuild the string to achieve the lexicographically largest string. This works because by sorting the special substrings in descending order, larger lexicographical strings are formed.
Time Complexity: O(n^2), where n is the length of the string, due to recursive decomposition and sorting.
Space Complexity: O(n), for storing the results and recursion stack.
1def makeLargestSpecial(s: str) -> str:
2 count = i = 0
3 res = []
4 for j, c in enumerate(s):
5 if c == '1':
6 count += 1
7 else:
8 count -= 1
9 if count == 0:
10 res.append('1' + makeLargestSpecial(s[i + 1:j]) + '0')
11 i = j + 1
12 return ''.join(sorted(res, reverse=True))
13The function recursively decomposes the string whenever a balance point is reached, i.e., when the count of '1's and '0's becomes zero. Once parts are decomposed, they are sorted in reverse (descending) order to achieve the lexicographically largest string.