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" 没办法进行任何转换。

提示：

• 1 <= binary.length <= 10⁵
• binary 仅包含 ‘0’ 和 ‘1’

---

解题分析及思路：

方法：贪心

思路：

此题可分两种情况：

• binary 不存在 0，返回binary
• binary 存在 0 的情况，如下

因为存在两种操作，一种是00 -> 10，一种是10 -> 01,那么对于任意字符串，最终都可以变成 1111…1110111..1 ，也就是n个1之间夹带一个0。

例如：

• 100 -> 110
• 000 -> 100 -> 110
• 10001 -> 11001 -> 11101
• 10010 -> 11010 -> 11001 -> 11101
• 诸如此类

从第一个为0的下标开始，后面所有的0都可以由 10 -> 01 操作往前聚集在一起，随后只要有两个相邻的0，都可以由00 -> 10操作消除第一个0。

所以最后只会剩下一个0，那么这个唯一的 0 的位置为 第一个为 0 的下标 + 0 的个数 - 1，即 zeroCount+firstZeroIndex-1。

func maximumBinaryString(binary string) string {
	var zeroCount int
	var firstZeroIndex int
	for index := len(binary) - 1; index >= 0; index-- {
		if binary[index] == '0' {
			zeroCount++
			firstZeroIndex = index
		}
	}
	if zeroCount == 0 {
		return binary
	}
	result := make([]byte, len(binary))
	for index := 0; index < len(binary); index++ {
		if index == zeroCount+firstZeroIndex-1 {
			result[index] = '0'
		} else {
			result[index] = '1'
		}
	}
	return string(result)
}

复杂度：

• 时间复杂度：O(N)
• 空间复杂度：O(N)

执行结果：

• 执行耗时:24 ms,击败了100.00% 的Go用户
• 内存消耗:6.7 MB,击败了61.54% 的Go用户