leetcode 763 划分字母区间

---

Contact me:

Blog -> https://cugtyt.github.io/blog/index
Email -> cugtyt@qq.com
GitHub -> Cugtyt@GitHub

---

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

示例 1:

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

注意:

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

思路：从头开始，不断寻找当前字母出现的下一个位置，扩大右边界，直到没有下一个位置为止，然后重新设置起点重复。

class Solution:
    def partitionLabels(self, S: str) -> List[int]:
        low = 0
        high = 0
        result = []
        while low < len(S):
            # find next S[low]
            newhigh = S.find(S[low], low + 1)
            # found
            if newhigh != -1:
                high = newhigh
                newlow = low
                while newlow <= high:
                    newhigh = S.find(S[newlow], newlow + 1)
                    if newhigh > high:
                        high = newhigh
                    newlow += 1
                result.append(high - low + 1)
            # not found
            else:
                result.append(1)
            
            low = high + 1
            high = high + 1
        return result