763. Partition Labels

key is

if (i == maxPartIndex) { // add to res,

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.

因為要 as many parts as possible parts, 所以要 greedy 的當有機會可以分 part 就分, 不然 part 只會變少, 所以當 index == maxPartIndex (part 最大的 index)時, 就可以分了, 不然part 只會更長

part_max_index = 8
 012345678   9012345
"ababcbaca | defegde | hijhklij"


index = 0, map get(a) = 8, maxPartIndex = 8
index = 1, map get(b) = 5
index = 2, map get(a) = 8
index = 3, map get(b) = 5
index = 4, map get(c) = 7
index = 5, map get(b) = 5
index = 6, map get(a) = 8
index = 7, map get(c) = 7
index = 8, map.get(a) = 8  => index == maxPartIndex == 8

index = 9, map.get(d) = 14
index = 10, map.get(e) = 15
index = 11, map.get(f) = 11
index = 12, map.get(e) = 15
index = 13, map.get(g) = 13
index = 14, map.get(d) = 14
index = 15, map.get(e) = 15

index = 16, map.get(h) = 19

O(n), O(1)

class Solution {
    public List<Integer> partitionLabels(String S) {
        // record the char last index
        // a index 8, 
        // if loop until max end equla current index, means it's a part, save len
        // s = index + 1, 
        int map[] = new int[26]; // S will consist of lowercase English letters ('a' to 'z') only.
        for (int i = 0; i < S.length(); i++) {
            char c = S.charAt(i);
            map[c - 'a'] = i;
        }
        List<Integer> res = new ArrayList<>();
        int start = 0;
        int end = 0;
        for (int i = 0; i < S.length(); i++) {
            end = Math.max(end, map[S.charAt(i) - 'a']); //注意要更新最大的 end
            if (end == i) {
                res.add(i - start + 1);
                start = i + 1;
            }
        }
        return res;
    }
}