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.
1import java.util.ArrayList;
2import java.util.Collections;
3
4class Solution {
5 public String makeLargestSpecial(String s) {
6 int count = 0, i = 0;
7 ArrayList<String> res = new ArrayList<>();
8 for (int j = 0; j < s.length(); j++) {
9 if (s.charAt(j) == '1') count++;
10 else count--;
11 if (count == 0) {
12 res.add('1' + makeLargestSpecial(s.substring(i + 1, j)) + '0');
13 i = j + 1;
14 }
15 }
16 Collections.sort(res, Collections.reverseOrder());
17 return String.join("", res);
18 }
19}This implementation is similar to the Python version. The string is decomposed at balancing points and stored in an ArrayList, which is then sorted in reverse order to get the largest arrangement.