Partition Labels

Problem Statement

Given a string s, partition it into as many parts as possible so that each letter appears in at most one part. Return the sizes of the parts in order.

Example

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

Two Pointer Approach

First record the last index of every character. Then scan with a start and an expanding end pointer: for each character, push end to the furthest last-occurrence seen so far. When the scan index reaches end, the partition is complete.

Complexity

• Time: O(n)
• Space: O(1) (fixed 26-letter table)

Solution Code

Python

def partitionLabels(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

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;
}

C++

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

Key Takeaways

• The start/end pair acts as an expanding two pointer window.
• A partition can close only when every seen letter’s last index is inside it.
• Precomputing last indices is what makes the single pass possible.