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 <stdio.h>
2#include <string.h>
3#include <stdlib.h>
4#include <stdbool.h>
5
6// Function prototypes
7char* makeLargestSpecial(const char* s);
8
9// Utility function
10int compare(const void* a, const void* b) {
11 return strcmp(*(const char**)b, *(const char**)a);
12}
13
14char* makeLargestSpecial(const char* s) {
15 int len = strlen(s);
16 int count = 0, i = 0, subIndex = 0;
17 char** substrings = (char**)malloc(len / 2 * sizeof(char*));
18 char* res = (char*)malloc(len + 1);
19
20 for (int j = 0; j < len; j++) {
21 s[j] == '1' ? count++ : count--;
22 if (count == 0) {
23 int size = j - i + 1;
24 char* sub = (char*)malloc(size + 1);
25 snprintf(sub, size + 1, "1%s0", makeLargestSpecial(s + i + 1));
26 substrings[subIndex++] = sub;
27 i = j + 1;
28 }
29 }
30
31 qsort(substrings, subIndex, sizeof(char*), compare);
32
33 res[0] = '\0';
34 for (int k = 0; k < subIndex; k++) {
35 strcat(res, substrings[k]);
36 free(substrings[k]);
37 }
38 free(substrings);
39 return res;
40}The code employs dynamic memory management for creating substrings and sorts them thereafter. qsort is used with a descending string comparison to reorder the string parts.