926.将字符串翻转到单调递增

将字符串翻转到单调递增

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

给你一个二进制字符串 s，你可以将任何 0 翻转为 1 或者将 1 翻转为 0。

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

示例 1:

输入：s = “00110”
输出：1

示例 2:

输入：s = “010110”
输出：2

提示:

• 1 <= s.length <= 10^5
• s[i] 为 ‘0’ 或 ‘1’

解析

使用动态规划，维护两个状态：dp0 表示当前位置为 0 的最小翻转次数，dp1 表示当前位置为 1 的最小翻转次数。

var minFlipsMonoIncr = function (s) {
  let dp0 = 0,
    dp1 = 0;

  for (const c of s) {
    const newDp0 = dp0 + (c === "1" ? 1 : 0);
    const newDp1 = Math.min(dp0, dp1) + (c === "0" ? 1 : 0);
    dp0 = newDp0;
    dp1 = newDp1;
  }

  return Math.min(dp0, dp1);
};

时间复杂度 O(n)，空间复杂度 O(1)。