字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一个字母只会出现在其中的一个片段。返回一个表示每个字符串片段的长度的列表。
示例 1：
输入：S = "ababcbacadefegdehijhklij" 输出：[9,7,8] 解释： 划分结果为 "ababcbaca", "defegde", "hijhklij"。 每个字母最多出现在一个片段中。 像 "ababcbacadefegde", "hijhklij" 的划分是错误的，因为划分的片段数较少。
提示：
S的长度在[1, 500]之间。 S只包含小写字母 'a' 到 'z' 。
来源：力扣（LeetCode）
这道题比较特殊，是要我们划分成尽可能小的区间，首先开头字母重复的都要被包含进去，这是必要条件，所以每一个字母最后出现的位置肯定是要获得的，用数组下标覆盖法先统计最后出现的位置。最短区间，假设就是由开头字母和最后一个出现的重复字母构成，（贪心算法解题的特点，每一次都期望获得一个最优值，而不管它是不是真的最优），所以我们只需检查当前最优区间是否满足“包含所有区间内字母们的重复值”即可，如果有其它重复的未被包含，那么就需要把尾部扩展至其它字母重复值也包含在内的位置。直到本区间检查完成，进入下一个区间。
class Solution { public List<Integer> partitionLabels(String S) { List<Integer> rs=new ArrayList<Integer>(); if(S==null || S.equals("")){ return rs; } //统计最后一个重复字母出现，不需要初始化，因为区间尾部必然>=0 int[] lc=new int[26]; char[] ss=S.toCharArray(); for(int i=0;i<ss.length;i++){ lc[ss[i]-'a']=i; } //检查区间 int s=0,e=lc[ss[s]-'a']; for(int i=0;i<ss.length;i++){ //本区间已完成 if(i==e){ rs.add(e-s+1); if(e<ss.length-1){ s=e+1; e=lc[ss[s]-'a']; } continue; } //区间需扩展 if(lc[ss[i]-'a']>e){ e=lc[ss[i]-'a']; } } return rs; } }
