题解

状态定义（$3$ 个阶段）

• 第 $0$ 段：开头连续的 $r$。
• 第 $1$ 段：中间连续的 $y$。
• 第 $2$ 段：末尾连续的 $r$。

用长度为 $3$ 的数组 $dp$ 表示处理到位置 $i$ 时的最少修改次数：

题目描述：

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

请你帮助小扣计算出他最少需要多少次调整操作才能将秋叶收藏集调整完毕。

输入：

一个字符串 $leaves$，表示秋叶收藏集。字符串的大小满足 $3 ≤ leaves.length ≤ 10^5$，并且字符串中仅包含字符 $r$ 和 $y$。

输出：

输出一个整数，表示最少需要的调整操作次数。

示例 1：

输入：

rrryyyrryyyrr

输出：

2

解释： 调整两次，将中间的两片红叶替换成黄叶，得到 "rrryyyyyyyyrr"。

示例 2：

输入：

ryr

输出：

0