标签划分

问题描述

给定一个字符串，将该字符串划分成尽可能多的部分，使得这些每个字母最多只能出现在这些部分中的一个

解决办法

首先获得每个字符最后出现的下标，然后从头开始遍历每一个字符，如果某个字符的范围超出当前划分的右边界，则扩展右边界，这是当前的最优解。直到遍历指针到达右边界，此时说明划分里的字符都是只出现在这个划分里的，将该划分放入答案中，然后把下一个下标作为下一个划分的起点，直到字符串遍历完。

class Solution {
    public List<Integer> partitionLabels(String S) {
        int[] last = new int[26];
        for (int i = 0; i < S.length(); ++i)
            last[S.charAt(i) - 'a'] = i;
        
        int j = 0, anchor = 0;
        List<Integer> ans = new ArrayList();
        for (int i = 0; i < S.length(); ++i) {
            j = Math.max(j, last[S.charAt(i) - 'a']);
            if (i == j) {
                ans.add(i - anchor + 1);
                anchor = i + 1;
            }
        }
        return ans;
    }
}