LeetCode-761. 特殊的二进制序列

LeetCode-761. 特殊的二进制序列

题目描述

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

0 的数量与 1 的数量相等。
二进制序列的每一个前缀码中 1 的数量要大于等于 0 的数量。
给定一个特殊的二进制序列 S，以字符串形式表示。定义一个操作 为首先选择 S 的两个连续且非空的特殊的子串，然后将它们交换。（两个子串为连续的当且仅当第一个子串的最后一个字符恰好为第二个子串的第一个字符的前一个字符。)

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

示例 1:

输入: S = "11011000"
输出: "11100100"

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

说明:

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

---

解题思路

思路

  本题采用分治法，对每一个01串进行如下操作：

• 排除首位 1 和末位 0
• 拆分成多个 特殊01串 并暂存
  • 使用一个标记位，当遇到1就+1，遇到0就-1，当标记位为0时则得到一个 子特殊01串
• 排序所有的 01串 并返回

关键结论

1. 每个特殊01串必然以 1 开始， 以 0 结束
2. 每个特殊01串若以首位1开始标记位拆分，则结果不一定是其本身
3. 标记位方法所得的拆分是最小拆分

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

空间复杂度：$O(n)$

代码

class Solution:
    def makeLargestSpecial(self, s: str) -> str:
        if len(s) <= 2:
            return s
    
        tmp = left = 0
        tmp_str = list()

        for i, ch in enumerate(s):
            tmp += 1 if ch == '1' else -1

            if tmp == 0:
                tmp_str.append('1' + self.makeLargestSpecial(s[left+1:i]) + '0')
                left = i + 1
        
        tmp_str.sort(reverse=True)

        return ''.join(tmp_str)

提交结果

时间——$\%66.67$

空间——$\%36.36$

---