Question

剑指 Offer II 092. 翻转字符

题目描述

如果一个由 '0' 和 '1' 组成的字符串，是以一些 '0'（可能没有 '0'）后面跟着一些 '1'（也可能没有 '1'）的形式组成的，那么该字符串是 单调递增 的。

我们给出一个由字符 '0' 和 '1' 组成的字符串 s，我们可以将任何 '0' 翻转为 '1' 或者将 '1' 翻转为 '0'。

返回使 s 单调递增 的最小翻转次数。

 

示例 1：

输入：s = "00110"
输出：1
解释：我们翻转最后一位得到 00111.

示例 2：

输入：s = "010110"
输出：2
解释：我们翻转得到 011111，或者是 000111。

示例 3：

输入：s = "00011000"
输出：2
解释：我们翻转得到 00000000。

 

提示：

• 1 <= s.length <= 20000
• s 中只包含字符 '0' 和 '1'

 

注意：本题与主站 926 题相同： https://leetcode.cn/problems/flip-string-to-monotone-increasing/

解法

方法一：枚举

我们先预处理得到右侧的 $0$ 的个数，记为 $right0$，初始化一个变量 $left0$，表示左侧的 $0$ 的个数。如果最终字符串变成全 '0' 或者全 '1'，那么答案为 $ans= \min(right0, n - right0)$。

接下来，我们枚举每个位置作为 '0' 和 '1' 的分界点（约定分界点为 '0'），计算出以当前位置为分界点的答案，最后取最小值即可。

时间复杂度 $O(n)$，其中 $n$ 是字符串的长度。空间复杂度 $O(1)$。

class Solution:
  def minFlipsMonoIncr(self, s: str) -> int:
    left0, right0 = 0, s.count("0")
    n = len(s)
    ans = min(right0, n - right0)
    for i, c in enumerate(s, 1):
      x = int(c)
      right0 -= x ^ 1
      left0 += x ^ 1
      ans = min(ans, i - left0 + right0)
    return ans

class Solution {
  public int minFlipsMonoIncr(String s) {
    int n = s.length();
    int left0 = 0, right0 = 0;
    for (int i = 0; i < n; ++i) {
      if (s.charAt(i) == '0') {
        ++right0;
      }
    }
    int ans = Math.min(right0, n - right0);
    for (int i = 1; i <= n; ++i) {
      int x = s.charAt(i - 1) == '0' ? 0 : 1;
      right0 -= x ^ 1;
      left0 += x ^ 1;
      ans = Math.min(ans, i - left0 + right0);
    }
    return ans;
  }
}

class Solution {
public:
  int minFlipsMonoIncr(string s) {
    int n = s.size();
    int left0 = 0, right0 = 0;
    for (char& c : s) {
      right0 += c == '0';
    }
    int ans = min(right0, n - right0);
    for (int i = 1; i <= n; ++i) {
      int x = s[i - 1] == '1';
      right0 -= x ^ 1;
      left0 += x ^ 1;
      ans = min(ans, i - left0 + right0);
    }
    return ans;
  }
};

func minFlipsMonoIncr(s string) int {
  n := len(s)
  left0, right0 := 0, 0
  for _, c := range s {
    if c == '0' {
      right0++
    }
  }
  ans := min(right0, n-right0)
  for i, c := range s {
    x := 0
    if c == '1' {
      x = 1
    }
    right0 -= x ^ 1
    left0 += x ^ 1
    ans = min(ans, i+1-left0+right0)
  }
  return ans
}

function minFlipsMonoIncr(s: string): number {
  const n = s.length;
  let [left0, right0] = [0, 0];
  for (const c of s) {
    right0 += c === '0' ? 1 : 0;
  }
  let ans = Math.min(right0, n - right0);
  for (let i = 1; i <= n; ++i) {
    const x = s[i - 1] === '0' ? 0 : 1;
    right0 -= x ^ 1;
    left0 += x ^ 1;
    ans = Math.min(ans, i - left0 + right0);
  }
  return ans;
}