题目

761. 特殊的二进制序列

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

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

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

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

示例 1:

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

说明:

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

思路

• 因为只能对连续且非空的特殊子串操作，所以声明一个变量在遍历过程中判断当前区间内是否为连续子串
• 因为0,1数量相等，且前缀中1的数量大于0，所以特殊字串由1开头，0结尾
• 不断递归所见的特殊字串，每次都求取其子串的最大字典序值，拼接后依旧是最大字典序
• 尽管只有两个相邻字符能够交换，但根据冒泡排序的原理，依旧可以获得升序列
• 上述的升序列即位所求值

代码

class Solution:
    def makeLargestSpecial(self, s: str) -> str:
        if len(s) <= 2:
            return s
        
        count = left = 0
        subs = list()
        for i, c in enumerate(s):
            if c == "1": count +=1
            else:
                count -= 1
                if count == 0:
                    subs.append("1" + self.makeLargestSpecial(s[left+1:i]) + "0")
                    left = i+1        
        subs.sort(reverse=True)
        return "".join(subs)

复杂度

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