A stringSof lowercase letters is given. We want to partition this string into as many parts as possible so that each letter appears in at most one part, and return a list of integers representing the size of these parts.

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.

Note:

1. Swill have length in range[1, 500].
2. Swill consist of lowercase letters ('a'to'z') only.

这题的思路大概是，先找出每一个字符对应的起始和终止的范围，然后再遍历字符串，如果当前字符和之前的所有字符的范围没有重叠，则把之前的范围加入结果，否则更新范围

class Solution {
    public List<Integer> partitionLabels(String S) {
        List<Integer> res = new ArrayList<Integer>();
        if(S == null || S.length() == 0)
            return res;

        HashMap<Character, int[]> map = new HashMap<>();
        char[] cs = S.toCharArray();

        for(int i = 0; i < cs.length; i++) {
            if(!map.containsKey(cs[i])) {
                map.put(cs[i], new int[]{i, i});
            }
            else {
                map.get(cs[i])[1] = i;
            }
        }

        int[] temp = null;
        for(int i = 0; i < cs.length; i++) {
            int[] range = map.get(cs[i]);
            if(temp == null) {
                temp = range;
            } else {
                if(range[0] >= temp[1]) {
                    res.add(temp[1] - temp[0] + 1);
                    temp = range;
                } else {
                    temp[0] = Math.min(temp[0], range[0]);
                    temp[1] = Math.max(temp[1], range[1]);
                }
            }
        }

        res.add(temp[1] - temp[0] + 1);

        return res;
    }
}