题目
字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一个字母只会出现在其中的一个片段。返回一个表示每个字符串片段的长度的列表。
示例 1：
输入：S = "ababcbacadefegdehijhklij"
输出：[9,7,8]
解释：划分结果为 "ababcbaca", "defegde", "hijhklij"。每个字母最多出现在一个片段中。像 "ababcbacadefegde", "hijhklij" 的划分是错误的，因为划分的片段数较少。
来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/partition-labels著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解答及思路
思路：先创建一个整型数组 list ，遍历字串将字母最后一次出现的信息存入数组。遍历字串，先确定子字串开始位置，如开始遍历时开始位置为0，一个子字串遍历结束后，开始位置调整为子字串结束位置+1；再确定结束位置，开始的结束位置是开始位置在数组中记录的值，在逐个遍历字串字符期间，若有字母最后出现位置超出结束位置，则更新结束位置为更大的结束位置；当遍历到结束位置，则意味着一个子字串遍历结束，记录字子串长度到集合ans中，并更新开始位置和结束位置，进行下一次子字串的遍历。
源码
class Solution {
public List<Integer> partitionLabels(String S) {
List<Integer> ans = new ArrayList<>();
if(S == ""||S == null){
return ans;
}
int[] list = new int[26];
for(int i = 0;i<S.length();i++){
list[S.charAt(i)-'a'] = i;
}
int first = 0;
int end = list[S.charAt(first)-'a'];
for(int i = 0;i<S.length();i++){
if(i == end){
ans.add(end-first+1);
if(end != S.length()-1){
first = i + 1;
end = list[S.charAt(first)-'a'];
}
}
if(list[S.charAt(i)-'a']>end)
end = list[S.charAt(i)-'a'];
}
return ans;
}
}
