题解 | #牛群分组#

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param s string字符串
# @return int整型一维数组
#
class Solution:
    def cowGrouping(self, s: str) -> List[int]:
        # write code here
        # 统计每个字母出现的次数
        letter_last_idx = {}  # 记录每个字母最后出现的位置
        result = []  # 存储每个分组的包含字母个数
        start, end = 0, 0  # 记录当前分组的起始和结束位置

        for i, char in enumerate(s):
            letter_last_idx[char] = i  # 更新字母最后出现的位置

        while end < len(s):
            current_char = s[end]
            max_last_idx = letter_last_idx[current_char]

            while end < max_last_idx:
                end += 1
                max_last_idx = max(max_last_idx, letter_last_idx[s[end]])

            result.append(end - start + 1)
            end += 1
            start = end

        return result