Partition Labels [Medium] — Greedy Last Occurrence

Problem Statement

Partition string s into as many parts as possible so each letter appears in at most one part. Return a list of part sizes.

Input: "ababcbacadefegdehijhklij"
Output: [9,7,8]

Intuition

Record the last index of each character. Sweep with a start and end. Update end = max(end, last[c]). When i == end, record partition.

Solutions

C++

vector<int> partitionLabels(string s) {
    int last[26]={};
    for (int i=0;i<s.size();i++) last[s[i]-'a']=i;
    vector<int> res;
    int start=0,end=0;
    for (int i=0;i<s.size();i++) {
        end=max(end,last[s[i]-'a']);
        if (i==end) { res.push_back(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;
}

JavaScript

var partitionLabels = function(s) {
    const last={};
    for (let i=0;i<s.length;i++) last[s[i]]=i;
    const res=[];
    let start=0,end=0;
    for (let i=0;i<s.length;i++) {
        end=Math.max(end,last[s[i]]);
        if (i===end) { res.push(end-start+1); start=i+1; }
    }
    return res;
};

Python

def partitionLabels(s: str) -> list[int]:
    last = {c: i for i, c in enumerate(s)}
    res, start, end = [], 0, 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

Complexity

Time: O(n)
Space: O(1) — 26-character alphabet