LeetCode 1702.修改后的最大二进制字符串：脑筋急转弯（构造，贪心）

【LetMeFly】1702.修改后的最大二进制字符串：脑筋急转弯（构造，贪心）

力扣题目链接：https://leetcode.cn/problems/maximum-binary-string-after-change/

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

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

<ul>
	<li>比方说， <code>"<strong>00</strong>010" -> "<strong>10</strong>010"</code></li>
</ul>
</li>
<li>操作 2 ：如果二进制串包含子字符串 <code>"10"</code> ，你可以用 <code>"01"</code> 将其替换。
<ul>
	<li>比方说， <code>"000<strong>10</strong>" -> "000<strong>01</strong>"</code></li>
</ul>
</li>

请你返回执行上述操作任意次以后能得到的 最大二进制字符串 。如果二进制字符串 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 <= 10⁵
binary 仅包含 '0' 和 '1' 。

解题方法：构造（贪心）

题目分析

如果给定字符串中没有0，则不在本次讨论的范围之列，直接返回原字符串。

推论1：最终字符串中一定有0

仅有的两种变换分别是00->10和10->01，只能减少0的个数，但永远不可能将所有0消除。

推论2：最终字符串中一定只有一个0

以10111011为例，该字符串中有两个0，则可以进行以下变换10111011->10011111->11011111，具体变换过程如下：

10111011
10110111 ---+
10101111    +---后面的那个0不断地通过10->01的变换最终和前面那个0相邻
10011111 ---+
11011111 -> 相邻两个0通过00->10的变换使得二进制字符串相比于初始值更大了

也就是说，假设最终字符串中有两个0，那么后面的那个0一定可以通过10->01的变换与前面的0相邻，相邻两个0再通过00->10变换，使得第一个0变成了1，字符串值更大了。

若有多个0则同理，最终一定只剩下一个0，变成111..11011..111的形态。

为什么不继续变化了呢？因为11、01都不可变，唯一可变的是10->01。但是这么变的话相当于“0往前移”了，字符串值更小，不可取。

如何判断最终字符串中0的位置？

由给定的两种变换00->10和10->01可以发现，0要么被消除（变换一）要么左移（变换二），单纯的左移会导致字符串变小，因此尽量将最前面的0“消除”。

如何消除？通过变换一消除。通过推论2我们知道，只要存在两个0，则右边的0必定能千里迢迢地来到左边的0身边并与之进行变换一：

111..11011..11011..11
111..11001..11111..11
111..11101..11111..11

也就是说，第一个0的右边每存在一个0，就能让第一个0的位置“右移一位”。

最终第一个0（也就是唯一的一个0）的位置，是原始字符串中第一个0的位置，再右移 $0 的总个数 - 1$ 位。

具体方法

给定字符串，统计其中0的个数（记为cnt0）。

若无0，则直接返回原始字符串；否则继续。

找到字符串中第一个0的位置（记为pos0），构造一个只有pos0 + cnt0 - 1这个位置为0其余位置全部为1的字符串并返回。

时空复杂度分析

时间复杂度 $O (l e n (bina ry))$
空间复杂度 $O (l e n (bina ry))$ ：空间复杂度来自字符串构造过程中的临时变量。

AC代码

C++

class Solution {
public:
    string maximumBinaryString(string binary) {
        int cnt0 = count(binary.begin(), binary.end(), '0');
        if (!cnt0) {
            return binary;
        }
        int first0 = binary.find('0');
        return string(first0 + (cnt0 - 1), '1') + '0' + string(binary.size() - (first0 + (cnt0 - 1)) - 1, '1');
    }
};

Python

class Solution:
    def maximumBinaryString(self, binary: str) -> str:
        cnt0 = binary.count('0')
        if not cnt0:
            return binary
        first0 = binary.find('0')
        pos0 = first0 + (cnt0 - 1)
        return '1' * pos0 + '0' + '1' * (len(binary) - pos0 - 1)