题目大意

字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。

一、示意图

在这里插入图片描述

二、解题思路

java实现（贪心算法）

代码如下：

class Solution {
       public List
   
     partitionLabels(String S) {
           //首先就是遍历字符号串，找到和起点相同的最后一个字母，查找这个区间里的字母最后的index是否超过        //区间，超出则更新区间，直到找到最大的index，那么index-i+1就是所求的区间长度，使用        //cache来存储每个字母最后出现的位置        if(S==null||S.length()==0){
               return null;        }        List
    
      res=new ArrayList<>();        int index,i,len=S.length();        //cache用来存最后的位置        int[]cache=new int[26];        //这里很妙        for(i=0;i
     
      index){
                       index=cache[S.charAt(j)-'a'];                }            }            //这里就进行对应的更新,index-i+1就是一组的内容大小            res.add(index-i+1);            i=index+1;        }          return res;         }}

在这里插入图片描述