763. Partition Labels

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.

将英文字母出现的首尾作为intervals看待。
根据字符创建数组并填入左右的index。
根据左侧index排序数组。

从左至右，如果intervals有交集，则合并。
否则在答案中添加当前interval的长度。

class Solution {
    public List<Integer> partitionLabels(String s) {
        int[][] alphabet = new int[26][2];
        int head = s.charAt(0) - 'a';
        for(int i = 0; i < s.length(); i++){
            int index = s.charAt(i) - 'a';
            if(head != index && alphabet[index][0] == 0) alphabet[index][0] = i;
            alphabet[index][1] = i;
        }
        
        Arrays.sort(alphabet, (a,b) -> a[0] - b[0]);
        
        List<Integer> ans = new ArrayList();
        int[] hold = alphabet[0];
        for(int i = 1; i < alphabet.length; i++){
            if(alphabet[i][0] <= hold[1]){
                hold[1] = Math.max(hold[1], alphabet[i][1]);
            }
            else{
                ans.add(hold[1]-hold[0]+1);
                hold = alphabet[i];
            }
        }
        ans.add(hold[1]-hold[0]+1);
        return ans;
        
    }
}