763. 划分字母区间

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

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

提示：

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

解题思路&代码

'''贪心策略

先将字符串 S 分析一遍，得到每个字母最后出现的位置

然后根据这个最后位置将字符串划分即可

划分的时候要以当前检索的字母为依据不断往后找，一直找到到该字母在后面没有出现过即可'''

class Solution:
    def partitionLabels(self, S: str) -> List[int]:
        n = []
        end = []
        j = 0
        l = len(S)
        for i in range(l):
            if S[i] not in n:
                n.append(S[i])
                end.append(i)
                j += 1
            else:
                for k in range(j):
                    if S[i] == n[k]:
                         end[k] = i
        i = 0
        count = []
        c = 0
        while i < l:
            x = end[n.index(S[i])]
            j = i
            while j < x :
                if end[n.index(S[j])] > x:
                    x = end[n.index(S[j])]
                j += 1
            if c == 0:
                count.append(x + 1)
            else:
                y = x + 1
                for k in range(c):
                    y = y - count[k]
                count.append( y )
            c += 1
            i = x + 1
        return count

大神简洁版：

class Solution:
   def partitionLabels(self, S: str) -> List[int]:
       #首先找到每个元素出现的最后位置,字典的形式，通过元素找到下标
       last={c:i for i,c in enumerate(S)}
       #设置区间
       start=end=0
       #保存字符串的长度
       res=[]
       #开始遍历元素"ababcbacadefegdehijhklij"
       for i,c in enumerate(S):
           #设置尾部
           end=max(end,last[c])
           #当区间里所有元素都遍历过
           if i==end:          
               res.append(end-start+1)
               start=i+1
       return res

参考资料：

Python查找某个元素索引
https://blog.csdn.net/julyli2019/article/details/109216331