763 Partition Labels

Leetcode

You are given a string s. We want to partition the string into as many parts as possible so that each letter appears in at most one part.

Note that the partition is done so that after concatenating all the parts in order, the resultant string should be s.

Return a list of integers representing the size of these parts.

Example 1:

Input: s = "ababcbacadefegdehijhklij"
Output: [9,7,8]
Explanation:
The partition is "ababcbaca", "defegde", "hijhklij".
This is a partition so that each letter appears in at most one part.
A partition like "ababcbacadefegde", "hijhklij" is incorrect, because it splits s into less parts.

Example 2:

Input: s = "eccbbbbdec"
Output: [10]

---

使用一个辅助数组记录每个字符最后出现的位置，由于分割的时候需要把所有相同字母分割在一起，遍历的时候不断判断当前字母最右位置，知道当前遍历的字母和最右位置重合。

public List<Integer> partitionLabels(String s) {
    int[] lastIndex=new int[128];
    List<Integer> ret=new ArrayList<>();
    for(int i=0;i<s.length();++i){
        lastIndex[s.charAt(i)]=i;
    }
    int left=0, right=0;
    for(int i=0;i<s.length();++i){
        int last=lastIndex[s.charAt(i)];
        if(last>right) right=last;
        if(i==right){
            ret.add(i-left+1);
            left=i+1;
        }
    }
    return ret;
}