难度: Hard
特殊的二进制序列是具有以下两个性质的二进制序列：
给定一个特殊的二进制序列 S，以字符串形式表示。定义一个操作 为首先选择 S 的两个连续且非空的特殊的子串，然后将它们交换。（两个子串为连续的当且仅当第一个子串的最后一个字符恰好为第二个子串的第一个字符的前一个字符。)
在任意次数的操作之后，交换后的字符串按照字典序排列的最大的结果是什么？
示例 1:
输入: S = "11011000" 输出: "11100100" 解释: 将子串 "10" （在S[1]出现） 和 "1100" （在S[3]出现）进行交换。 这是在进行若干次操作后按字典序排列最大的结果。
说明:
S 的长度不超过 50。S 保证为一个满足上述定义的特殊 的二进制序列。运行时间: 28 ms
内存: 0.0 MB
class Solution:
def makeLargestSpecial(self, S: str) -> str:
count = 0
i = 0
res = []
for (j, ch) in enumerate(S):
if ch == '1':
count += 1
else:
count -= 1
if count == 0:
res.append('1' + self.makeLargestSpecial(S[i + 1:j]) + '0')
i = j + 1
res.sort(reverse=True)
return "".join(res)
此题解采用的是递归分治策略。首先，它通过遍历字符串S，利用计数器count来确定特殊二进制序列的一个完整子序列（即0和1数量相等的序列）。每当count归零时，找到了一个特殊子序列。此时，该特殊子序列又以递归方式调用makeLargestSpecial来进一步分解和排序，直到不能再分解。接着，将这个子序列加上头尾的'1'和'0'，将其加入结果列表res中。完成整个字符串的遍历后，对列表res中的所有序列按字典序逆序进行排序，最后合并为一个字符串作为最终结果。这个过程确保了最终的字符串是所有可能操作后的字典序最大值。
时间复杂度: O(n log n)
空间复杂度: O(n)
class Solution:
def makeLargestSpecial(self, S: str) -> str:
count = 0
i = 0
res = []
# 遍历字符串S
for (j, ch) in enumerate(S):
if ch == '1':
count += 1
else:
count -= 1
# 当找到一个完整的特殊子序列
if count == 0:
# 递归处理内部的特殊序列并添加头尾'1'和'0'
res.append('1' + self.makeLargestSpecial(S[i + 1:j]) + '0')
i = j + 1
# 对所有子序列进行逆序排序以获得字典序最大的字符串
res.sort(reverse=True)
return ''.join(res)
通过遍历子字符串并维护一个计数器来确定是否满足条件。初始计数器为0，遍历字符串中的每个字符，遇到'1'则计数器加1，遇到'0'则计数器减1。如果在任何时刻计数器变为负，则说明存在一个前缀其中0的数量多于1的数量，此时子字符串不满足条件。只有当遍历结束时计数器恢复为0，且在整个遍历过程中计数器没有变为负，才能确定该子字符串满足特殊二进制序列的定义。
在递归分治策略中，每找到一个满足条件的特殊子序列，都会进行递归处理以确保子序列自身是最大的字典序。处理完所有子序列后，将它们逆序排序的原因是，更大的子序列如果排在前面，会使得合并后的整体字典序更大。这是因为在字典序排序中，字符串的开始部分权重更大。因此，通过将最大的子序列放在最前面，然后依次降序排列，确保了整体字符串在字典序上尽可能大。
递归处理去掉首尾'1'和'0'的中间部分是因为，根据题目的定义，一个特殊的二进制序列必须以'1'开头，以'0'结尾，且内部的子序列也须满足特殊二进制序列的要求。因此，首尾的'1'和'0'是固定的，只需要递归处理中间部分以确定如何使这部分达到最大字典序。这种处理方式不会丢失潜在的最大字典序排列，因为任何更大的排列也必须符合特殊二进制序列的定义，即以'1'开头和'0'结尾，且内部满足特殊序列的要求。