题目描述

小扣出去秋游，途中收集了一些红叶和黄叶，他利用这些叶子初步整理了一份秋叶收藏集 leaves，字符串 leaves 仅包含小写字符 r 和 y，其中字符 r 表示一片红叶，字符 y 表示一片黄叶。
出于美观整齐的考虑，小扣想要将收藏集中树叶的排列调整成「红、黄、红」三部分。每部分树叶数量可以不相等，但均需大于等于 1。每次调整操作，小扣可以将一片红叶替换成黄叶或者将一片黄叶替换成红叶。请问小扣最少需要多少次调整操作才能将秋叶收藏集调整完毕。

样例

输入：leaves = "rrryyyrryyyrr"
输出：2
解释：调整两次，将中间的两片红叶替换成黄叶，得到 "rrryyyyyyyyrr"。

输入：leaves = "ryr"
输出：0
解释：已符合要求，不需要额外操作。

限制

• 3 <= leaves.length <= 10^5
• leaves 中只包含字符 'r' 和字符 'y'。

算法

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

1. 将 「红、黄、红」 看做三个阶段，设 $f_0(i)$ 表示以 $i$ 结尾且处于阶段 0 的最少操作次数，$f_1(i)$ 表示处于阶段 1 的最少操作次数，$f_2(i)$ 表示处于阶段 2 的最少操作次数。有效下标从 0 开始。
2. 初始时，如果第一个字符为 r，则 $f_0(0) = 0$，否则 $f_1(0) = 1$。其余为无穷。
3. 转移时，则阶段 0 只能从阶段 0 转移，阶段 1 可以从阶段 0 或 1 转移，阶段 2 可以从阶段 1 或 2 转移。根据当前字符和阶段来判断本次是否需要调整操作。
4. 最终答案为 $f_2(n-1)$。可以通过调整每轮三个阶段的转移顺序，来优化空间为常数。

时间复杂度

• 状态数为 $O(n)$，转移时间为常数，故总时间复杂度为 $O(n)$。

空间复杂度

• 优化后，仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    int minimumOperations(string leaves) {
        const int n = leaves.size();
        int f0, f1 = n + 1, f2 = n + 1;
        if (leaves[0] == 'r') f0 = 0;
        else f0 = 1;

        for (int i = 1; i < n; i++) {
            if (leaves[i] == 'r') {
                f2 = min(f1, f2);
                f1 = min(f0, f1) + 1;
            } else {
                f2 = min(f1, f2) + 1;
                f1 = min(f0, f1);
                f0 = f0 + 1;
            }
        }

        return f2;
    }
};