763. 划分字母区间

解法一：数学+枚举

记录每个字母首次出现和最后一次出现的位置。要分成尽可能多的区间，那么所有可能的分段位置应该放在每个字母的最后出现位置后。进一步筛选得到正确答案，这个位置还必须满足不能将其他字母的出现区域划分成两块。
有了以上分析，候选项不超过26个，筛选完后进行升序排序，并求出相邻的差值即可得到题目要求的输出结果。

import java.util.*;
class Solution {
    public List<Integer> partitionLabels(String S) {
        // 每个字母首次出现的下标+1
        int[] first = new int[26];
        // 每个字母最后一次出现的下标+1
        int[] last = new int[26];
        for (int i = 0, index; i < S.length(); ++i) {
            index = S.charAt(i) - 97;
            if (first[index] == 0) {
                first[index] = i + 1;
                last[index] = i + 1;
            } else {
                last[index] = i + 1;
            }
        }
        List<Integer> list = new ArrayList<>();
        List<Integer> ans = new ArrayList<>();
        for (int index : last) {
            if (index == 0) {
                continue;
            }
            boolean flag = true;
            // 在此处截断是否会将其他字母分成两部分
            for (int i = 0; i < 26; ++i) {
                if (first[i] == 0) {
                    continue;
                }
                if ((first[i] <= index) && (index < last[i])) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                list.add(index);
            }
        }
        list.sort(Integer::compareTo);
        if (!list.isEmpty()) {
            ans.add(list.get(0));
        }
        for (int i = 1; i < list.size(); ++i) {
            ans.add(list.get(i) - list.get(i - 1));
        }
        return ans;
    }
}