秋叶收藏集

难度: Medium

小扣出去秋游，途中收集了一些红叶和黄叶，他利用这些叶子初步整理了一份秋叶收藏集 `leaves`，字符串 `leaves` 仅包含小写字符 `r` 和 `y`，其中字符 `r` 表示一片红叶，字符 `y` 表示一片黄叶。出于美观整齐的考虑，小扣想要将收藏集中树叶的排列调整成「红、黄、红」三部分。每部分树叶数量可以不相等，但均需大于等于 1。每次调整操作，小扣可以将一片红叶替换成黄叶或者将一片黄叶替换成红叶。请问小扣最少需要多少次调整操作才能将秋叶收藏集调整完毕。 **示例 1：** >输入：`leaves = "rrryyyrryyyrr"` > >输出：`2` > >解释：调整两次，将中间的两片红叶替换成黄叶，得到 "rrryyyyyyyyrr" **示例 2：** >输入：`leaves = "ryr"` > >输出：`0` > >解释：已符合要求，不需要额外操作 **提示：** - `3 <= leaves.length <= 10^5` - `leaves` 中只包含字符 `'r'` 和字符 `'y'`

Submission

运行时间: 285 ms

内存: 16.5 MB

class Solution:
    def minimumOperations(self, leaves: str) -> int:
        # 枚举黄红分界点，同时加上前面最少的红黄分界点
        # 最左边的部分，r越多，y越少越好
        r = y = 0
        if leaves[0] == 'r':
            r += 1
        else:
            y += 1
        left = [r - y, r, y]

        total_r = leaves.count('r')
        # 最多不需要改的字符数
        mx = 0
        for c in leaves[1:-1]:
            if c == 'r':
                r += 1
            else:
                y += 1
            mx = max(mx, total_r - r + left[1] + y - left[2])
            if r - y > left[0]:
                left = [r - y, r, y]
        return len(leaves) - mx

Explain

该题解采用了动态规划的思想，目标是将字符串调整为红黄红三部分的形式。我们可以将问题看作是在一序列中寻找两个点，将序列分为三部分，并对这三部分进行调整以达到目标形式。题解中，通过枚举黄红分界点的位置，同时计算前面最少的红黄分界点。首先，初始化计算首位置的红叶和黄叶数量，然后逐一检查每个叶子，更新当前的红叶和黄叶数量，并计算不需要调整的字符的最大值。最终，需要的调整次数是总叶子数减去不需要调整的最大字符数。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def minimumOperations(self, leaves: str) -> int:
        # 初始化红叶和黄叶的数量
        r = y = 0
        if leaves[0] == 'r':
            r += 1
        else:
            y += 1
        left = [r - y, r, y]  # 存储红黄分界点的差值、红叶总数和黄叶总数

        total_r = leaves.count('r')  # 总红叶数
        # 初始化最多不需要改的字符数
        mx = 0
        for c in leaves[1:-1]:
            if c == 'r':
                r += 1
            else:
                y += 1
            # 更新不需要调整的最大字符数
            mx = max(mx, total_r - r + left[1] + y - left[2])
            # 更新最优红黄分界点
            if r - y > left[0]:
                left = [r - y, r, y]
        # 返回需要调整的最少次数
        return len(leaves) - mx

Explore

在动态规划中采用‘红黄分界点的差值’（r-y）、‘红叶总数’和‘黄叶总数’作为状态表示，主要是因为这些状态能够有效地描述当前遍历到的叶子位置前所有叶子的累计属性，并为后续的状态转移提供必要的信息。‘红黄分界点的差值’（r-y）帮助我们定位到在当前和之前的叶子中，哪个位置的累积红黄叶差值最大，这有助于确定最优的红黄分界点位置。通过记录这些信息，算法可以在遍历叶子时动态调整和计算不同分界点情况下的最优解，而不需要对每一个可能的分界点进行独立计算，从而大大提高了效率。

公式`total_r - r + left[1] + y - left[2]`用于计算在当前叶子位置作为黄红分界点时，不需要调整的最大字符数。这里，`total_r`代表整个叶子序列中的红叶总数。`r`是当前位置之前的红叶数，`y`是当前位置之前的黄叶数。`left[1]`代表在之前的最优分界点之前的红叶总数，`left[2]`代表在之前的最优分界点之前的黄叶总数。这个公式实际上计算的是，固定当前位置作为黄红分界点，找到之前最优的红黄分界点（使得红黄差值最大），并计算通过这种分割方式能够保持不变的红叶和黄叶的数量，从而推导出最少需要调整的叶子数量。

在枚举过程中，关注‘r - y’是否大于‘left[0]’的原因是为了更新并寻找最优的红黄分界点。这里，‘r - y’表示当前位置的红叶和黄叶的差值，而‘left[0]’存储之前遍历过程中遇到的最大的红黄叶差值。如果当前的‘r - y’大于‘left[0]’，说明在当前位置之前存在一个更优的红黄分界点，可以使得红叶和黄叶之间的差值更大，这对于之后的黄红转换会更有利。因此，更新这个最大差值和对应的统计数值（红叶总数和黄叶总数），可以帮助算法在后续的计算中找到更少调整次数的方案。