Question

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

English Version

题目描述

给你一个二进制字符串 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' 。

解法

方法一：脑筋急转弯

我们观察发现，操作 2 可以把所有的 $1$ 都移动到字符串的末尾，而操作 1 可以把所有的 0000..000 串变为 111..110。

因此，要想得到最大的二进制串，我们应该把所有不在开头的 $1$ 移动到字符串末尾，使得字符串变为 111..11...00..11 的形式，然后借助操作 1 把中间的 000..00 变为 111..10。这样我们最终可以得到一个最多包含一个 $0$ 的二进制字符串，这个字符串就是我们要求的最大二进制串。

时间复杂度 $O(n)$，其中 $n$ 为字符串 binary 的长度。忽略答案的空间消耗，空间复杂度 $O(1)$。

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

class Solution {
  public String maximumBinaryString(String binary) {
    int k = binary.indexOf('0');
    if (k == -1) {
      return binary;
    }
    int n = binary.length();
    for (int i = k + 1; i < n; ++i) {
      if (binary.charAt(i) == '0') {
        ++k;
      }
    }
    char[] ans = binary.toCharArray();
    Arrays.fill(ans, '1');
    ans[k] = '0';
    return String.valueOf(ans);
  }
}

class Solution {
public:
  string maximumBinaryString(string binary) {
    int k = binary.find('0');
    if (k == binary.npos) return binary;
    int n = binary.size();
    for (int i = k + 1; i < n; ++i) {
      if (binary[i] == '0') {
        ++k;
      }
    }
    return string(k, '1') + '0' + string(n - k - 1, '1');
  }
};

func maximumBinaryString(binary string) string {
  k := strings.IndexByte(binary, '0')
  if k == -1 {
    return binary
  }
  for _, c := range binary[k+1:] {
    if c == '0' {
      k++
    }
  }
  ans := []byte(binary)
  for i := range ans {
    ans[i] = '1'
  }
  ans[k] = '0'
  return string(ans)
}