题目描述

给你一个仅由字符 '0' 和 '1' 组成的字符串 s。一步操作中，你可以将任一 '0' 变成 '1'，或者将 '1' 变成 '0'。

交替字符串 定义为：如果字符串中不存在相邻两个字符相等的情况，那么该字符串就是交替字符串。例如，字符串 "010" 是交替字符串，而字符串 "0100" 不是。

返回使 s 变成 交替字符串 所需的 最少 操作数。

样例

输入：s = "0100"
输出：1
解释：如果将最后一个字符变为 '1'，s 就变成 "0101"，即符合交替字符串定义。

输入：s = "10"
输出：0
解释：s 已经是交替字符串。

输入：s = "1111"
输出：2
解释：需要 2 步操作得到 "0101" 或 "1010"。

限制

• 1 <= s.length <= 10^4
• s[i] 是 '0' 或 '1'。

算法1

(分类讨论) $O(n)$

1. 分别求出以 0 开头的合法字符串和以 1 开头的合法字符串的最少操作次数，取二者中的最小值。

时间复杂度

• 遍历字符串两次，故总时间复杂度为 $O(n)$。

空间复杂度

• 需要 $O(n)$ 的额外空间临时存储字符串。

C++ 代码

class Solution {
private:
    int calc(string s, char start) {
        int res = 0;
        if (s[0] != start) {
            s[0] = start;
            res++;   
        }

        const int n = s.size();
        for (int i = 1; i < n; i++) {
            if (s[i] != s[i - 1]) continue;
            if (s[i] == '1') s[i] = '0';
            else s[i] = '1';
            res++;
        }
        return res;
    }

public:
    int minOperations(string s) {
        return min(calc(s, '0'), calc(s, '1'));
    }
};

算法2

(动态规划) $O(n)$

1. 设 $f(i)$ 表示考虑了以位置 $i$ 为结尾的字符串，且最终以 0 结尾的最小操作次数。$g(i)$ 表示考虑了以位置 $i$ 为结尾的字符串，且最终以 1 结尾的最小操作次数。
2. 初始时，根据首个字符分别初始化 $f(0)$ 和 $g(0)$。
3. 转移时，如果当前位置为 0，则 $f(i) = g(i - 1)$，$g(i) = f(i - 1) + 1$。如果当前位置为 1，则 $g(i) = f(i - 1)$，$f(i) = g(i - 1) + 1$。
4. 最终答案为 $\min(f(n - 1), g(n - 1))$。
5. 由于每次转移仅与上一个位置有关，故可以优化空间。

时间复杂度

• 动态规划的状态为 $O(n)$，每次仅需要常数的时间转移，故总时间复杂度为 $O(n)$。

空间复杂度

• 仅需要常数的额外空间。

Go 代码

func minOperations(s string) int {
    var s0, s1 int
    if s[0] == '0' {
        s0, s1 = 0, 1
    } else {
        s0, s1 = 1, 0
    }

    n := len(s)
    for i := 1; i < n; i++ {
        if s[i] == '0' {
            s0, s1 = s1, s0 + 1
        } else {
            s0, s1 = s1 + 1, s0
        }
    }
    if s0 < s1 {
        return s0
    }
    return s1
}