763. Partition Labels

Posted on | Edited on | Views:

LeetCode

Approach: Greedy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public List<Integer> partitionLabels(String S) {
        int[] last=new int[26];
        for(int i=0;i<S.length();i++){
            last[S.charAt(i)-'a']=i;
        }
        int j=0,anchor=0;
        List<Integer> ans=new ArrayList<>();
        for(int i=0;i<S.length();i++){
            j=Math.max(j,last[S.charAt(i)-'a']);
            if(i==j){
                ans.add(i-anchor+1);
                anchor=i+1;
            }
        }
        return ans;
    }
}

0%