题目

字符串 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;

    }

}