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.
1var makeLargestSpecial = function(s) {
2 let count = 0, i = 0;
3 let res = [];
4 for (let j = 0; j < s.length; j++) {
5 s.charAt(j) === '1' ? count++ : count--;
6 if (count === 0) {
7 res.push('1' + makeLargestSpecial(s.substring(i + 1, j)) + '0');
8 i = j + 1;
9 }
10 }
11 res.sort((a, b) => b.localeCompare(a));
12 return res.join('');
13};The JavaScript function segments the string using a similar logic as other languages, sorts the fragments in descending order to produce the largest attempt result.