题解 | #分品种#

• 题目考察的知识点 : 贪心算法,双指针
• 题目解答方法的文字分析：

1. 创建一个长度为 26 的数组 last，用于记录每个字母在字符串 s 中最后出现的位置。
2. 遍历字符串 s，对于每个字母，将其最后出现的位置记录到 last 数组中。
3. 使用双指针技巧来计算每个子串的长度。具体而言，遍历字符串 s，并记录当前待划分子串的起始位置 start 和结束位置 end，其中 end 表示当前待划分子串中最后一个字母最后出现的位置。
4. 如果当前位置 i 等于 end，说明当前子串已经达到最优划分，可以将其长度添加到结果列表 partition 中，并将指针 start 更新为 end + 1，开始处理下一个待划分子串。

• 本题解析所用的编程语言: Python
• 完整且正确的编程代码

class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        n = len(s)
        last = [-1] * 26

        # 记录每个字母在字符串 s 中最后出现的位置
        for i in range(n):
            last[ord(s[i]) - ord('a')] = i

        partition = []
        start, end = 0, 0

        # 使用双指针技巧计算每个子串的长度
        for i in range(n):
            end = max(end, last[ord(s[i]) - ord('a')])

            if i == end:
                partition.append(end - start + 1)
                start = end + 1

        return partition