困难

问题描述

特殊的二进制序列是具有以下两个性质的二进制序列：

• 0 的数量与 1 的数量相等。
• 二进制序列的每一个前缀码中 1 的数量要大于等于 0 的数量。

给定一个特殊的二进制序列 S，以字符串形式表示。定义一个操作 为首先选择 S 的两个连续且非空的特殊的子串，然后将它们交换。（两个子串为连续的当且仅当第一个子串的最后一个字符恰好为第二个子串的第一个字符的前一个字符。)

在任意次数的操作之后，交换后的字符串按照字典序排列的最大的结果是什么？

示例 1:

输入: S = "11011000"
输出: "11100100"
解释:
将子串 "10" （在 S[1]出现） 和 "1100" （在 S[3]出现）进行交换。
这是在进行若干次操作后按字典序排列最大的结果。

说明:

• S 的长度不超过 50。
• S 保证为一个满足上述定义的特殊的二进制序列。

递归

对于一个特殊序列而言，它一定以 $1$ 开始，以 $0$ 结束。这是因为：

• 长度为 $1$ 的前缀中 $1$ 的数量一定要大于等于 $0$ 的数量，所以首位一定是 $1$
• 由于 $0$ 和 $1$ 的数量相等，并且任意前缀中 $1$ 的数量一定大于等于 $0$ 的数量，所以末位一定是 $0$

按照特殊序列要求拆分成多个特殊子序列，若子序列内部仍然存在特殊子序列，则继续递归拆分，最终得到一组特殊子序列，将特殊子序列组按字典序从大到小排列后合并成字符串即为该特殊序列的字典序最大形式，局部的最大字典序排列最终归并后会得到整体的最大字典序排列。

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

• 时间复杂度：$O(n^2)$
• 空间复杂度：$O(n)$