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.
1#include <vector>
2#include <string>
3#include <algorithm>
4
5class Solution {
6public:
7 std::string makeLargestSpecial(std::string s) {
8 int count = 0, i = 0;
9 std::vector<std::string> res;
10 for (int j = 0; j < s.size(); ++j) {
11 s[j] == '1' ? ++count : --count;
12 if (count == 0) {
13 res.push_back("1" + makeLargestSpecial(s.substr(i + 1, j - i - 1)) + "0");
14 i = j + 1;
15 }
16 }
17 std::sort(res.begin(), res.end(), std::greater<std::string>());
18 return std::accumulate(res.begin(), res.end(), std::string(""));
19 }
20};The function utilizes vector for storing parts and sorts them in descending order using a custom comparator. The recursion captures and processes each balanced segment in the input string.