难度：★★★☆☆
类型：字符串
方法：逻辑

力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录

字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。

示例：

输入：S = "ababcbacadefegdehijhklij"
输出：[9,7,8]
解释：
划分结果为 "ababcbaca", "defegde", "hijhklij"。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 的划分是错误的，因为划分的片段数较少。

提示：

S的长度在[1, 500]之间。
S只包含小写字母 'a' 到 'z' 。

解答

理解一下题目的需要，关键语句是：划分字符串，条件是：任意字符串中任意字母不在其他字符串中出现。

我们首先需要确定所有字符在字符串中出现过的最后位置，存在一个字典last_appear中，表达了字符和最后位置的对应关系。

为了标记每个片段的起止位置，我们定义两个整型变量start和end，并初始化为零，然后循环遍历S字符串中所有字符c（对应的位置是i），注意，在遍历过程中终止位置end是要不断更新的，或者说随着遍历到的字符最后出现位置不断向后推，在代码上用end = max(last_appear[c], end)来表达，这样操作的目的在于，保证从start到end位置中的所有字符，都只出现在本子串中。

直到当前位置i到达了本子串的结尾位置end，就可以将end作为子串终点了。在记录结果的同时，更新一下下一个子串的开始位置start。

代码很简单：

class Solution:
    def partitionLabels(self, S):
        last_appear = {c: i for i, c in enumerate(S)}
        ans = list()
        start = end = 0
        for i, c in enumerate(S):
            end = max(last_appear[c], end)
            if i == end:
                ans.append(end - start + 1)
                start = end + 1
        return ans

如有疑问或建议，欢迎评论区留言~

有关更多力扣中等题的python解决方案，请移步力扣中等题解析