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

力扣第 42 场双周赛第 3 题

题目

给你一个二进制字符串 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" 没办法进行任何转换。

提示：

• 1 <= binary.length <= 105
• binary 仅包含 '0' 和 '1' 。

相似问题：

• 2311：小于等于 K 的最长二进制子序列（1839 分）

分析

• 观察操作二，可以将 0 往前移
• 因此只要存在多个 0，就可以移到一起用操作一替换
• 所以最终结果必然只有一个 0 或没有 0
• 最终一个 0 的情况，计算其下标即可

解答

1
2
3
4
5
6
7

class Solution:
    def maximumBinaryString(self, binary: str) -> str:
        i = binary.find('0')
        if i<0:
            return binary
        j = i+binary.count('0')-1
        return '1'*j+'0'+'1'*(len(binary)-1-j)

65 ms