**题目：**字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一个字母只会出现在其中的一个片段。返回一个表示每个字符串片段的长度的列表。 示例： 提示： 解题思路： 由于同一个字母只能出现在同一个片段，显然同一个字母的第一次出现的下标位置和最后一次出现的下标位置必须出现在同一个片段。因此需要遍历字符串，得到每个字母最后一次出现的下标位置 方法：贪心算法+双指针
class Solution { public List<Integer> partitionLabels(String S) { List<Integer> res=new ArrayList<Integer>(); int n=S.length(); int[] letter=new int[26]; for(int i=0;i<n;i++) { letter[S.charAt(i)-'a']=i; } int start=0,end=0; for(int i=0;i<n;i++) { end=Math.max(end, letter[S.charAt(i)-'a']); if(i==end) { res.add(end-start+1); start=end+1; } } return res; } }