# 0763. Partition Labels
###### tags: `Leetcode` `Medium` `FaceBook` `Merge Interval-Jump Game`
Link: https://leetcode.com/problems/partition-labels/
## 思路 $O(N)$ $O(1)$
首先traverse一次，记录每个字母最后出现的位置
然后首先拿一个字母，看它最后出现的位置在哪，于是产生了一个substring，遍历这个substring不断扩充这个partition的长度，直到不再扩充了，就把长度加进答案里面，以此循环。
和[55.Jump Game](https://hackmd.io/BLDJgdvVR2yk2ZZka2dArg) merge的思路很像
## Code

class Solution {
    public List<Integer> partitionLabels(String s) {
        int[] last = new int[26];
        for(int i = 0;i < s.length();i++){
            last[s.charAt(i)-'a']=i;
        }
        int idx = 0;
        List<Integer> ans = new ArrayList<>();
        int prev = 0;
        while(idx<s.length()){
            int end = last[s.charAt(idx)-'a'];
            for(;idx<=end && idx<s.length();idx++){
                end = Math.max(end, last[s.charAt(idx)-'a']);
            }
            ans.add(idx-prev);
            prev = idx;
        }
        return ans;
    }
}