暴力递归、分治排序递归 2 算法，分割和合并字符串，求解《761. 特殊的二进制序列》

var makeLargestSpecial = function(s) {
  const n = s.length
  for (let i = 0; i < n; i++) {
    if (s[i] === '0') continue
    let cnt = 1, s1 = '', s2 = '', k = 0
    for (let j = i + 1; j < n; j++) {
      if (s[j] === '1') cnt++
      else if (--cnt === 0) {
        if (s1 === '') {
          s1 = s.substring(i, j + 1)
          k = j + 1
        } else {
          s2 = s.substring(k, j + 1)
          if (gt(s2, s1)) return makeLargestSpecial(s.substring(0, i) + s2 + s1 + s.substring(j + 1))
        }
      }
    }
  }
  return s
};
const gt = (a, b) => {
  const m = a.length, n = b.length
  let i = j = 0
  while (a[i] === b[j] && i < m && j < n) {
    i++
    j++
  }
  return a[i] > b[j]
}

var makeLargestSpecial = function(s) {
  const n = s.length
  if (n <= 2) return s
  for (let i = 0; i < n; i++) {
    if (s[i] === '0') continue
    let cnt = 1, k = 0
    for (let j = i + 1; j < n; j++) {
      if (s[j] === '1') cnt++
      else if (--cnt === 0) {
        if (k === 0) k = j + 1
        else if (gt(s, i, k, j)) return makeLargestSpecial(s.substring(0, i) + s.substring(k, j + 1) + s.substring(i, k) + s.substring(j + 1))
      }
    }
  }
  return s
};
const gt = (s, i, k, j) => {
  const m = k
  while (s[i] === s[k] && i < m && k <= j) {
    i++
    k++
  }
  return s[k] > s[i]
}

var makeLargestSpecial = function(s) {
  const n = s.length, r = []
  if (n <= 2) return s
  let cnt = 0, start = 0
  for (let i = 0; i < n; i++) {
    if (s[i] === '1') cnt++
    else if (--cnt === 0) {
      r.push('1' + makeLargestSpecial(s.substring(start + 1, i)) + '0')
      start = i + 1
    }
  }
  return r.sort().reverse().join('')
};

function makeLargestSpecial(s: string): string {
  const n = s.length, r = []
  if (n <= 2) return s
  let cnt = 0, start = 0
  for (let i = 0; i < n; i++) {
    if (s[i] === '1') cnt++
    else if (--cnt === 0) {
      r.push('1' + makeLargestSpecial(s.substring(start + 1, i)) + '0')
      start = i + 1
    }
  }
  return r.sort().reverse().join('')
};

class Solution {
  function makeLargestSpecial($s) {
    $n = strlen($s);
    if ($n <= 2) return $s;
    $r = [];
    $cnt = 0;
    $start = 0;
    for ($i = 0; $i < $n; $i++) {
      if ($s[$i] === '1') $cnt++;
      else if (--$cnt === 0) {
        $r []= '1' . $this->makeLargestSpecial(substr($s, $start + 1, $i - $start - 1)) . '0';
        $start = $i + 1;
      }
    }
    rsort($r, SORT_STRING);
    return implode('', $r);
  }
}

import "sort"
func makeLargestSpecial(s string) string {
  n, r, start, cnt := len(s), []string{}, 0, 0
  if n <= 2 {
    return s
  }
  for i, c := range s {
    if c == '1' {
      cnt++
    } else {
      cnt--
      if cnt == 0 {
        var sb strings.Builder
        sb.WriteByte('1')
        sb.WriteString(makeLargestSpecial(s[start + 1:i]))
        sb.WriteByte('0')
        r = append(r, sb.String())
        start = i + 1
      }
    }
  }
  sort.Sort(sort.Reverse(sort.StringSlice(r)))
  return strings.Join(r, "")
}

class Solution {
  public String makeLargestSpecial(String s) {
    int n = s.length();
    if (n <= 2) return s;
    int cnt = 0, start = 0;
    List<String> r = new ArrayList<String>();
    for (int i = 0; i < n; i++) {
      if (s.charAt(i) == '1') cnt++;
      else if (--cnt == 0) {
        StringBuilder sb = new StringBuilder();
        sb.append("1");
        sb.append(makeLargestSpecial(s.substring(start + 1, i)));
        sb.append("0");
        r.add(sb.toString());
        start = i + 1;
      }
    }
    Collections.sort(r, (a, b) -> b.compareTo(a));
    return String.join("", r);
  }
}

public class Solution {
  public string MakeLargestSpecial(string s) {
    int n = s.Length;
    if (n <= 2) return s;
    int start = 0, cnt = 0;
    List<string> r = new List<string>();
    for (int i = 0; i < n; i++) {
      if (s[i] == '1') cnt++;
      else if(--cnt == 0) {
        StringBuilder sb = new StringBuilder();
        sb.Append("1");
        sb.Append(MakeLargestSpecial(s.Substring(start + 1, i - start - 1)));
        sb.Append("0");
        r.Add(sb.ToString());
        start = i + 1;
      }
    }
    r.Sort((a, b) => b.CompareTo(a));
    return string.Join("", r);
  }
}

static inline int cmp (const void * pa, const void * pb) {
  return strcmp(*(char **)pb, *(char **)pa);
}
char * d(char * s, int l, int r) {
  int n = r - l;
  if (n <= 2) {
    char *t = (char *)malloc(sizeof(char) * (n + 1));
    strncpy(t, s + l, n);
    t[n] = '\0';
    return t;
  };
  char** ans = malloc(sizeof(char *) * n);
  int cnt = 0, start = l, pos = 0;
  for (int i = l; i < r; ++i) {
    if (s[i] == '1') cnt++;
    else if (--cnt == 0) {
      char *t = d(s, start + 1, i);
      ans[pos] = (char *)malloc(sizeof(char) * (strlen(t) + 3));
      sprintf(ans[pos], "%s%s%s", "1", t, "0");
      start = i + 1;
      pos++;
    }
  }
  qsort(ans, pos, sizeof(char*), cmp);
  char *t = (char *)malloc(sizeof(char) * (n + 1));
  int j = 0;
  for (int i = 0; i < pos; i++) {
    j += sprintf(t + j, "%s", ans[i]);
    free(ans[i]);
  }
  t[j] = '\0';
  return t;
}
char * makeLargestSpecial(char * s){
  return d(s, 0, strlen(s));
}

class Solution {
public:
  string makeLargestSpecial(string s) {
    int n = s.size();
    if (n <= 2) return s;
    int cnt = 0, start = 0;
    vector<string> r;
    for (int i = 0; i < n; i++) {
      if (s[i] == '1') cnt++;
      else if (--cnt == 0) {
        r.push_back("1" + makeLargestSpecial(s.substr(start + 1, i - start - 1)) + "0");
        start = i + 1;
      }
    }
    sort(r.begin(), r.end(), greater<string>());
    string t = accumulate(r.begin(), r.end(), ""s);
    return t;
  }
};

class Solution:
  def makeLargestSpecial(self, s: str) -> str:
    n = len(s)
    if n <= 2: return s
    cnt, start, r = 0, 0, []
    for i, c in enumerate(s):
      if c == '1': cnt += 1
      else:
        cnt -= 1
        if cnt == 0:
          r.append('1' + self.makeLargestSpecial(s[start + 1:i]) + '0')
          start = i + 1
    return ''.join(sorted(r, reverse=True))