1702. 修改后的最大二进制字符串

题目

给你一个二进制字符串 binary ，它仅有 0 或者 1 组成。你可以使用下面的操作任意次对它进行修改：

操作 1 ：如果二进制串包含子字符串 "00" ，你可以用 "10" 将其替换。

比方说， "00010" -> "10010"

操作 2 ：如果二进制串包含子字符串 "10" ，你可以用 "01" 将其替换。

比方说， "00010" -> "00001"

请你返回执行上述操作任意次以后能得到的 最大二进制字符串 。如果二进制字符串 x 对应的十进制数字大于二进制字符串 y 对应的十进制数字，那么我们称二进制字符串 x 大于二进制字符串 y 。

示例 1：


输入：binary = "000110"
输出："111011"
解释：一个可行的转换为：
"000110" -> "000101"
"000101" -> "100101"
"100101" -> "110101"
"110101" -> "110011"
"110011" -> "111011"

示例 2：


输入：binary = "01"
输出："01"
解释："01" 没办法进行任何转换。

解法

此题的数据量很大(10^5), 必须找到线性复杂度的方法才能解决。

我们从左往右地逐一处理，一开始我们只考虑前两个字符，然后逐步往尾部增加字符来考虑。分析情况之后，我们会发现，该问题的局部最优解即是全局最优解，即我们可以用贪心法来解决。

我们只需考虑尾部两个字符的情况：

00: 转换为 10

10: 如果前面还存在 0, 比如 xxx01110, 则我们可以通过连续转换(10->01)得到 xxx10111

11: 保持不变

01: 保持不变

由于字符串在 python 中是不可直接修改的，使用字符串拼接的开销也很大，我们可以用列表来存储字符，最后在将其拼接成字符串，但是可惜这个操作仍然会超时。

观察规律，我们会发现，由以上四种操作后，我们的结果字符串中最多只出现一个 0。因而我们唯一需要保存的就是这个 0 出现的位置。

还有一种直观的思维方式：

通过操作 10->01, 我们可以把所有的 1 都放到低位，所有的 0 都放到高位。

通过操作 00->10, 我们可以把高位连续的 00000 变成 11110

代码


class Solution:
    def maximumBinaryString(self, binary: str) -> str:
        if len(binary) < 2:
            return binary

        ans = [binary[0], binary[1]]
        if ans == ['0', '0']:
            ans = ['1', '0']
        idx0 = 0 if ans[0] == '0' else -1
        
        lastChr = ans[-1]
        for i in range(2, len(binary)):
            c = binary[i]
            if lastChr + c == '01':
                idx0 = i - 1
                lastChr = '1'
            elif lastChr + c == '00':
                lastChr = '0'
            elif lastChr + c == '10':
                if idx0 > -1:
                    idx0 += 1
                    lastChr = '1'
                else:
                    lastChr = '0'
            else:
                lastChr = '1'
        
        return '1' * (len(binary) - 1) + lastChr if idx0 < 0 else '1' * idx0 + '0' + '1' * (len(binary) - idx0 - 1)