1702. 修改后的最大二进制字符串（Rating 1825）

以下内容偏向于记录个人练习过程及思考，非常规题解内容

题目

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

Rating 1825

思路

让二进制字符串最大，需要尽可能的让左边都是1

按照操作规则，0可以一直向左挪动，两个0可以换成10

考虑从左到右遍历，找到第一个0出现的位置

如果后面还有0，那么可以把它移动过来，换成10

因此，我们可以把第一个0后面的1全部移到最右边，然后把中间所有的000…00变成111…10即可

灵神的题解提供了一些反证法的证明。

代码

class Solution:
    def maximumBinaryString(self, binary: str) -> str:
        cnt0, cnt1 = 0, 0
        flag = 1
        ret = ''
        for c in binary:
            if flag and c == '1': # 找第一个0的位置
                ret += '1' # 前面的1保留在答案里
                continue
            flag = 0
            cnt0 += c == '0' # 统计第一个0的位置后面的0的个数
            cnt1 += c == '1' # 统计第一个0的位置后面的1的个数
        if cnt0 == 0: # 如果没有0，直接返回原字符串
            return binary
        return ret + (cnt0 - 1) * '1' + '0' + cnt1 * '1' # 中间所有的000...00变成111...10