Partition Labels

Medium Problem 139 of 151 Java and Python

Problem

Given a string s, split 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 1

Input: s = "ababcbacadefegdehijhklij"
Output: [9, 7, 8]
Why: "ababcbaca", "defegde", "hijhklij".

Example 2

Input: s = "eccbbbbdec"
Output: [10]

Constraints

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

Explanation

Once a part contains a letter, it must stretch at least to that letter's last occurrence. So record every letter's last index, then scan: keep extending the current part's end to the furthest last-index seen. When the scan reaches that end, the part can close.

Approach 1 · Naive

Grow each part, checking the rest

Time O(n²)
Space O(1)

Start a part and keep extending it while any of its letters still appears later in the string.

From start, set end = start.
While some letter in s[start..end] appears after end, increase end.
Record the size and start the next part at end + 1.

Java

import java.util.*;

class Solution {
    public List<Integer> partitionLabels(String s) {
        List<Integer> sizes = new ArrayList<>();
        int start = 0;
        while (start < s.length()) {
            int end = start;
            for (int i = start; i <= end; i++) {
                end = Math.max(end, s.lastIndexOf(s.charAt(i)));
            }
            sizes.add(end - start + 1);
            start = end + 1;
        }
        return sizes;
    }
}

Python

class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        sizes, start = [], 0
        while start < len(s):
            end = i = start
            while i <= end:
                end = max(end, s.rindex(s[i]))
                i += 1
            sizes.append(end - start + 1)
            start = end + 1
        return sizes

Approach 2 · Optimal

Last index table, one scan

Time O(n)
Space O(1) (26 letters)

Precompute each letter's last index; scan once, extending end and closing a part when i == end.

last[c] = last index of each letter.
Scan i: end = max(end, last[s[i]]).
If i == end, record end - start + 1 and set start = i + 1.

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

Python

class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        last = {c: i for i, c in enumerate(s)}
        sizes, start, end = [], 0, 0
        for i, c in enumerate(s):
            end = max(end, last[c])
            if i == end:
                sizes.append(end - start + 1)
                start = i + 1
        return sizes

Complexity compared

Approach	Time	Space
Naive Grow each part, checking the rest	O(n²)	O(1)
Optimal Last index table, one scan	O(n)	O(1) (26 letters)

Key takeaways

This is Merge Intervals in disguise: each letter is an interval from its first to its last index.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem