Partition Labels

Medium

Python

def partition_labels(s):
    last={c:i for i,c in enumerate(s)}
    res=[]; start=end=0
    for i,c in enumerate(s):
        end=max(end,last[c])
        if i==end:
            res.append(end-start+1)
            start=i+1
    return res

Java

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;
    List<Integer> res=new ArrayList<>();
    int start=0,end=0;
    for(int i=0;i<s.length();i++){
        end=Math.max(end,last[s.charAt(i)-'a']);
        if(i==end){res.add(end-start+1);start=i+1;}
    } return res;
}

Key Insight

Greedy partitioning. Dict comprehension vs int[26].

Python → Java Differences

Dict comprehension vs int[26]
Greedy partition identical
enumerate vs manual index

Python

def partition_labels(s):
    last={c:i for i,c in enumerate(s)}
    res=[]; start=end=0
    for i,c in enumerate(s):
        end=max(end,last[c])
        if i==end:
            res.append(end-start+1)
            start=i+1
    return res

Java

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;
    List<Integer> res=new ArrayList<>();
    int start=0,end=0;
    for(int i=0;i<s.length();i++){
        end=Math.max(end,last[s.charAt(i)-'a']);
        if(i==end){res.add(end-start+1);start=i+1;}
    } return res;
}

Algorithm Steps

1. Track last occurrence
2. Expand end to last of current
3. Partition when i==end

← Previous All Greedy