【算法】763. 划分字母区间

题目：

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

 

示例 1：

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

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

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/partition-labels 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

声明：

解题思路和代码原创： https://leetcode-cn.com/problems/partition-labels/solution/zui-jian-dan-jie-shi-bi-guan-jie-hao-dong-duo-liao/

本人是小白，对代码和解题思路做了一个更详细的补充。

解题思路

1. 看见开头一个字母，就要看这个字母最后出现在哪，然后康康这个开头和结尾之间的那些其他字母是不是都落在这个区间里，
2. 如果区间内的字母最后位置不在区间内，就拿这个字母的位置来扩大区间，如果是，什么也不做。
3. 对于这道题，比较巧妙的点是：利用字典key的唯一性，记录一个字母最大的index是哪里的字典max_index。
4. 然后，遍历字符串的字母和位置，跟max_index比较对应字母的index，此处用max来获得字母的最大index。
5. 如果当前遍历字母的最大index大，那就说明超过了边界，那就要更新边界。

代码

class Solution:
    def partitionLabels(self, S: str) -> List[int]:
        max_index = {item: idx for idx, item in enumerate(S)}  # 键值转换，得到一个{字母：index}的max_index字典
        start, end = 0, 0  # 定义字符串的起始边界， 结束边界
        ans = []
        for idx, i in enumerate(S):
         # 这里就是用边界和当前遍历到的字母的最大index去比较，看看谁大，
         # 如果当前字母的位置，小于max_index最大index大就扩充边界end。
         # 提示：这里的end，在每一次循环中，都会设定为当前字母的边界end，只是用于下边的if idx ==end 使用。
            end = max(end, max_index[i])
            if idx == end:  # 当前遍历的字母和位置idx如果和max_indexx中对应字母的位置一致，说明当前的for循环已经遍历了这个字母的所有位置。
                ans.append(end - start + 1)
                start = idx + 1 # start只为新字符串设定开始位置，所以在没找到当前字符串的end位时，start的值是不变的。
        return ans