# 763. Partition Labels

{% embed url="<https://leetcode.com/problems/partition-labels/>" %}

不知道是该叫它`sliding window`还是`三指针`...

先设置双指针`l,r`，从头开始遍历：

1. 将右指针`r`直接移动到目前遇到的字符所出现的最后一个位置（最右位置）
2. 然后对左右指针之间的字符进行遍历（`i`指针），根据遇到的字符去扩展目前`i`遍历的右边界（即`r`，只扩大，不回缩），直到`i`和`r`相交（即`l`与`r`之间的所有字符都不会再在右侧出现），记录一下当前长度为一个结果。
3. 将`l`指针移到`r`的右边，开始下一个对`i`的遍历。

```python
class Solution:
    def partitionLabels(self, S: str) -> List[int]:
        count = collections.Counter(S)
        rightMost = {ch: S.rindex(ch) for ch in count.keys()}
        
        res = []
        l, r = 0, 0
        ## step 1
        while l < len(S) and r < len(S):
            r = rightMost[S[l]]
            ## step 2
            i = l
            while i != r:
                r = max(r, rightMost[S[i]])
                i += 1
            res.append(r-l+1)
            ## step 3
            l = r+1

        return res
```
