Partition Labels

Problem

Given a string of lowercase letters, partition it into as many parts as possible so that each letter appears in at most one part. Return the list of part lengths.

Constraints

• 1 ≤ s.length ≤ 500
• s contains only lowercase English letters

Approach — Two Pointers

This is a Two Pointers problem. The idea: walk two indices through the data together (or toward each other), turning an O(n²) pair search into one linear pass. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(n) time, O(1) extra space.

Solution code

Python

class Solution:
    def partitionLabels(self, 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

import java.util.*;

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;
        List<Integer> out = 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) {
                out.add(end - start + 1);
                start = i + 1;
            }
        }
        return out;
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.