128.Partition Labels

MediumGreedy · 7/8

Problem

You are given a string s. Split it into as many parts as possible such that each letter appears in at most one part. Concatenating the parts in order must give back s.

Return a list of the sizes of these parts.

Examples

Input:  s = "ababcbacadefegdehijhklij"
Output: [9,7,8]
Explanation: "ababcbaca", "defegde", "hijhklij". No letter appears in two parts.
             "ababcbacadefegde" would also be valid but gives fewer parts.

Input:  s = "eccbbbbdec"
Output: [10]
Explanation: 'e' appears at index 0 and 8 and 'c' at 9, so everything must stay together.

Input:  s = "abc"
Output: [1,1,1]

Constraints

1 <= s.length <= 500
s consists of lowercase English letters.

💡 Key Insight

Once a part contains a letter, it must extend at least to that letter's last occurrence. So scan left to right while keeping end = max(last[c]) over the letters seen in the current part. When the index i reaches end, nothing inside the part appears later — cut there. Cutting as early as possible is always safe, so this greedy produces the maximum number of parts.

Brute Force Expansion

TimeO(n²)SpaceO(1)

Intuition

Start a part at start. Its end must be at least the last occurrence of s[start]. But every letter between start and that end may push the end further, so keep scanning, and for each character search the rest of the string for its last occurrence. When the scan reaches the current end, close the part.

Algorithm

start = 0.
While start < n: end = lastIndexOf(s[start]); for i from start while i <= end, set end = max(end, s.lastIndexOf(s[i])).
Record end - start + 1, set start = end + 1.

Visualization

s = "eccbbbbdec"
start=0, 'e' last at 8 -> end=8
i=1 'c' last at 9 -> end=9
... i reaches 9 -> part size 10

Code

java

import java.util.ArrayList;
import java.util.List;

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

Complexity

Time: O(n²) — lastIndexOf is O(n) and is called for every character.
Space: O(1) — excluding the output.

Merge Letter Intervals

TimeO(n)SpaceO(1)

Intuition

Each letter occupies an interval [first, last]. Two letters whose intervals overlap must be in the same part. So the parts are exactly the merged intervals — the classic merge-intervals routine. Since letters ordered by first occurrence are already sorted by start, no extra sort is needed if we walk the string.

Algorithm

Record first[c] and last[c] for each letter.
Walk the string; at each first occurrence of a letter, consider interval [first[c], last[c]].
If it starts after the current merged interval's end, close the current part and start a new one; otherwise extend the end.
Close the final part.

Visualization

s = "ababcbacadefegdehijhklij"
a:[0,8] b:[1,5] c:[4,7] d:[9,14] e:[10,15] f:[11,11] g:[13,13]
h:[16,19] i:[17,22] j:[18,23] k:[20,20] l:[21,21]

merge: [0,8]  |  [9,15]  |  [16,23]   -> sizes 9, 7, 8

Code

java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public List<Integer> partitionLabels(String s) {
        int[] first = new int[26];
        int[] last = new int[26];
        Arrays.fill(first, -1);
        for (int i = 0; i < s.length(); i++) {
            int c = s.charAt(i) - 'a';
            if (first[c] == -1) {
                first[c] = i;
            }
            last[c] = i;
        }

        List<Integer> sizes = new ArrayList<>();
        int curStart = 0, curEnd = -1;
        for (int i = 0; i < s.length(); i++) {
            int c = s.charAt(i) - 'a';
            if (first[c] != i) {
                continue; // only consider each letter's interval once
            }
            if (first[c] > curEnd && curEnd >= 0) {
                sizes.add(curEnd - curStart + 1); // no overlap: close part
                curStart = first[c];
            }
            curEnd = Math.max(curEnd, last[c]);
        }
        sizes.add(curEnd - curStart + 1);
        return sizes;
    }
}

Complexity

Time: O(n) — two passes over the string.
Space: O(1) — two arrays of 26.

Greedy with Last OccurrenceOptimal

TimeO(n)SpaceO(1)

Intuition

We don't even need first occurrences. Precompute last[c]. Scan once, stretching end to last[s[i]]. Whenever i == end, every letter in [start, end] has its last occurrence inside the part, so close it. This is the same merge idea compressed into a single pass with two pointers.

Algorithm

last[c] = last index of each letter.
start = 0, end = 0.
For each i: end = max(end, last[s[i]]); if i == end, record end - start + 1 and set start = i + 1.
Return the sizes.

Dry Run

flowchart LR
    A["i=0 'a'<br/>end = 8"] --> B["i=1..7<br/>b:5, c:7 keep end = 8"]
    B --> C["i=8 == end<br/>cut size 9"]
    C --> D["i=9 'd' end=14<br/>i=10 'e' end=15"]
    D --> E["i=15 == end<br/>cut size 7"]
    E --> F["i=16 'h' end=19<br/>i=17 'i' end=22<br/>i=18 'j' end=23"]
    F --> G["i=23 == end<br/>cut size 8"]

Code

java

import java.util.ArrayList;
import java.util.List;

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, end = 0;
        for (int i = 0; i < s.length(); i++) {
            end = Math.max(end, last[s.charAt(i) - 'a']); // part must reach this letter's last spot
            if (i == end) {
                sizes.add(end - start + 1); // every letter in the part is closed
                start = i + 1;
            }
        }
        return sizes;
    }
}

Complexity

Time: O(n) — two passes.
Space: O(1) — a fixed array of 26 (excluding the output).

Complexity Comparison

Approach	Time	Space
Brute Force Expansion	O(n²)	O(1)
Merge Letter Intervals	O(n)	O(1)
Greedy with Last Occurrence	O(n)	O(1)

Common Pitfalls

Using only the last occurrence of the first letter of a part — letters inside the part can push the end further.
Returning the parts themselves instead of their sizes.
Forgetting to reset start = i + 1 after each cut, which makes every size cumulative.
Using a HashMap for last positions works but is unnecessary; an int[26] is faster and simpler.