题目

763. 划分字母区间【中等】

题解

根据提示里的内容可以做出个大半了，中心思想就是贪心

Try to greedily choose the smallest partition that includes the first letter. If you have something like “abaccbdeffed”, then you might need to add b. You can use an map like “last[‘b’] = 5” to help you expand the width of your partition.

class Solution {
    
    public List<Integer> partitionLabels(String s) {
    
        int n=s.length();
        List<Integer>res=new ArrayList<>();
        //字符最后出现的位置
        int[] last=new int[26];
        for(int i=0;i<n;i++){
    
            last[s.charAt(i)-'a']=i;
        }
        int i=0;
        while(i<n){
    
            int end=last[s.charAt(i)-'a'];
            for(int j=i+1;j<=end;j++){
    
                end=Math.max(end,last[s.charAt(j)-'a']);
            }
            res.add(end-i+1);
            i=end+1;
        }
        return res;
    }
}

时间复杂度：$O(n)$，看着是双重循环，但是 i 和 j 其实可以视为一个指针，共同遍历字符串s一次，所以复杂度其实只是O(n)

空间复杂度：$O(S)$