Difficulty: MediumGreedy

Partition Labels

Problem in Plain English

You are given a string and must split it into as many contiguous parts as possible so that no letter ever appears in more than one part. Return the length of each part in order.

Problem Statement

You are given a string s. Partition s into as many parts as possible so that each letter appears in at most one part.

The parts must be contiguous and, concatenated in order, must reconstruct s. Return a list of integers holding the size of each part.

Constraints

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

Examples

Example 1

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

The parts are "ababcbaca", "defegde" and "hijhklij", with sizes 9, 7 and 8. Splitting into fewer parts, such as merging the first two, would still be valid but not maximal.

Example 2

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

The letters e and c appear at both the start and the end, so the whole string is one part of size 10.

Example 3

Input: s = "a"
Output: [1]

One character is already one valid part. There is no boundary inside it, so the maximum number of parts is one.

Example 4

Input: s = "abacbdef"
Output: [5,1,1,1]

The first a forces the range through index 2, but b at index 1 reappears at 4 and extends it to abacb. Letters d, e and f each occur once and form separate parts. Cutting after aba would split the two b occurrences.

Intuition

Every occurrence of a letter must remain in one part. Seeing a at index 0 in Example 1 therefore forces the part through its last occurrence at 8. Letters discovered inside that forced range may extend it again. The first position where no encountered letter reaches farther is the earliest legal cut; taking every such cut produces as many parts as possible.

Approaches

Repeated Last Search

Solution Details

Reveal Repeated Last Search: intuition, complexity, and code

Intuition

A part must stretch past the last occurrence of every letter it contains, so growing a window until no inside letter reaches beyond it always closes a valid part. The cost is rescanning the string for the last occurrence of each letter again and again.

Step-by-Step Logic

At each unprocessed start index, find the last occurrence of its letter and initialize end to that index. Example 1 starts at 0 with a ending at 8.
Scan every position from start through the current end, searching the whole string for that letter last position. Extend end when necessary, and continue through any newly added positions. The loop must use the changing end, not a fixed original bound.
When the scan passes end, emit end - start + 1 and begin the next part at end + 1. Example 1 emits 9 at end 8, then starts at 9.
Repeat until the string is consumed. For Example 1, e extends the second part from end 14 to 15; the third expands from h at 19 through j at 23. Return [9,7,8].
The dry-run end column starts each new window after its initial last-occurrence search: end is 8 at start 0, 14 at start 9, and 19 at start 16. Emit rows represent finishing that window scan.

Why It Works

For a part starting at start, its end must reach the last occurrence of every letter encountered before the proposed cut. The maintained end is the largest such last position. If the scan has not reached end, an encountered letter still has an occurrence on the right, so cutting now is illegal. When the scan reaches end, every letter in the part finishes there or earlier, so the cut is valid. This is the earliest legal cut. Any valid partition whose first part ends later can replace that first part with this one and partition the remaining suffix without losing a part; repeating the argument gives the maximum number of parts.

Dry Run

Repeated Last Search: variable states at each step
j	Letter	Last position	End transition	Action	Output so far
0	a	8	8 -> 8	continue	[]
1	b	5	8 -> 8	continue	[]
2	a	8	8 -> 8	continue	[]
3	b	5	8 -> 8	continue	[]
4	c	7	8 -> 8	continue	[]
5	b	5	8 -> 8	continue	[]
6	a	8	8 -> 8	continue	[]
7	c	7	8 -> 8	continue	[]
8	a	8	8 -> 8	emit 9; next start 9	[9]
9	d	14	14 -> 14	continue	[9]
10	e	15	14 -> 15	continue	[9]
11	f	11	15 -> 15	continue	[9]
12	e	15	15 -> 15	continue	[9]
13	g	13	15 -> 15	continue	[9]
14	d	14	15 -> 15	continue	[9]
15	e	15	15 -> 15	emit 7; next start 16	[9,7]
16	h	19	19 -> 19	continue	[9,7]
17	i	22	19 -> 22	continue	[9,7]
18	j	23	22 -> 23	continue	[9,7]
19	h	19	23 -> 23	continue	[9,7]
20	k	20	23 -> 23	continue	[9,7]
21	l	21	23 -> 23	continue	[9,7]
22	i	22	23 -> 23	continue	[9,7]
23	j	23	23 -> 23	emit 8; next start 24	[9,7,8]

Complexity Analysis

Time Complexity

O(n^2)

Space Complexity

O(1)

Let n be the string length and k the number of returned parts. Across all windows, each character triggers one last-occurrence search taking O(n) worst-case time, hence O(n^2) time. The scans keep O(1) auxiliary indices and do not allocate substrings. The returned list uses O(k) space; here k is at most 26 because parts have disjoint nonempty lowercase-letter sets, so total space is O(1) under the fixed alphabet. With an unbounded alphabet, output storage would be O(k).

Code

Solution.java

1import java.util.List;2import java.util.ArrayList;3
4class Solution {5    public List<Integer> partitionLabels(String s) {6        List<Integer> res = new ArrayList<>();7        int i = 0;8        while (i < s.length()) {9            int start = i;10            int end = s.lastIndexOf(s.charAt(i));11            // The endpoint may grow: inspect newly included letters before cutting.12            for (int j = i; j <= end; j++) {13                int last = s.lastIndexOf(s.charAt(j));14                if (last > end) {15                    end = last;16                }17            }18            res.add(end - start + 1);19            i = end + 1;20        }21        return res;22    }23}

Hints

Hint 1

A part ending at index e must extend past the last occurrence of every letter inside it.

Hint 2

Knowing every letter final position in advance turns the repeated rescanning into one table lookup.

Hint 3

Sweep once while carrying the farthest last occurrence seen so far, and cut a part exactly when the sweep index reaches it.

Edge Cases

A single-character string yields [1]; the scan cuts as soon as its only index reaches end.
All distinct letters, such as "abc", split into all ones: [1, 1, 1].
A letter tying the first and last positions, like e in "eccbbbbdec", forces one part covering the whole string.
Nested or overlapping letter ranges, as in abacbdef, require repeated endpoint expansion before a cut.
At most 26 parts can be returned because each nonempty part must own a letter used by no other part.

Common Mistakes and Interview Tips

Cutting a part at the last occurrence of its first letter without extending for letters discovered inside the part.
Forgetting to move the part start to end + 1 after a cut, which double-counts the boundary character.
Using end - start instead of end - start + 1 loses the inclusive final character.
Assigning end to the current letter last position can shrink a boundary forced by an earlier letter; retain the maximum.
Scanning only to the original endpoint misses letters pulled in by later extensions.
Interview tip: proving each cut is valid is insufficient; show why it is the earliest possible cut and therefore maximizes the number of parts.

Key Takeaway

When each item pulls in everything linked to it, precomputing the farthest reach of every item turns repeated expansion into one greedy sweep.