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.
1using System;
2using System.Collections.Generic;
3using System.Linq;
4
5public class Solution {
6 public string MakeLargestSpecial(string s) {
7 int count = 0, i = 0;
8 List<string> res = new List<string>();
9 for (int j = 0; j < s.Length; j++) {
10 if (s[j] == '1') count++;
11 else count--;
12 if (count == 0) {
13 res.Add('1' + MakeLargestSpecial(s.Substring(i + 1, j - i - 1)) + '0');
14 i = j + 1;
15 }
16 }
17 res.Sort((a, b) => string.Compare(b, a));
18 return string.Concat(res);
19 }
20}This C# solution captures the concept of recursion and sorting into a List, which then uses the Sort method with descending comparison to align the special substrings.