Module 5 · String Greedy

Partition Labels

MediumProblem 13 of 21 8 min read ~15 min to solve LeetCode

GreedyStringLast OccurrenceTwo PointersIntervals

Asked atAmazonGoogleMicrosoftMetaApple

Problem Statement

You are given a lowercase string s. Split it into as many parts as possible so that each letter appears in at most one part. Return a list of the sizes of those parts in order.

Input

A lowercase string s.

Output

A list of integers, where each integer is the length of one partition and every character appears in at most one partition.

Constraints

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

Examples

Example 1

Input:

s = ababcbacadefegdehijhklij

Output: [9,7,8]

Explanation: The partitions are ababcbaca, defegde, and hijhklij. No letter crosses partition boundaries.

Example 2

Input:

s = eccbbbbdec

Output: [10]

Explanation: The early e must stay with the final e, and that span also contains all occurrences of c, b, and d, so the whole string is one partition.

Learning Objectives

Convert character last occurrences into greedy boundary constraints.
Recognise when a partition can safely close as soon as all seen letters are contained.
Explain why cutting at the first safe boundary maximises the number of partitions.
Implement a linear scan with constant extra character metadata.

Intuition

Greedy Insight: When a partition starts, every character you see creates an obligation: the partition must extend at least to that character's last occurrence. So keep a running end equal to the farthest last occurrence among characters in the current partition.

The moment the scan index reaches end, all obligations created inside the partition have been satisfied. Closing immediately is safe and best, because delaying the cut can only make this partition larger and reduce the number of remaining partitions.

Common mistakes

×Cutting when the current character reaches its own last occurrence, instead of checking the farthest last occurrence of every character seen in the partition.
×Trying every possible split, which misses the fact that each character gives a direct boundary requirement.
×Forgetting to reset the partition start after closing a partition.
×Building maps of character positions when only the last occurrence is needed.

Algorithm Explanation

Greedy strategy Precompute the last index of every character. Sweep from left to right, extending the current partition end to the farthest last occurrence of any character seen so far. When the current index equals that end, close the partition immediately.

Why it works Before index end, at least one character inside the current partition still appears later, so any earlier cut would violate the rule. At index end, every character seen since start has its final occurrence inside start...end, so the cut is valid.

Proof of correctness Consider an optimal solution. The first partition cannot end before the greedy end, because some character from the first partition would appear outside it. If the optimal first partition ends after the greedy end, exchange that longer first partition for the greedy shorter valid partition. This does not make any later partition invalid, because no character inside the greedy partition appears later. The remaining suffix is at least as long to partition as before, so the number of partitions is no worse. Repeating this exchange for each suffix shows the greedy cuts are optimal.

Algorithm

Record last[c], the final index of each lowercase character.
Initialise start = 0 and end = 0.
For each index i, update end = max(end, last[s[i]]).
If i == end, append end - start + 1 to the answer and set start = i + 1.
Return all partition lengths.

Solutions

Solution: Last occurrence sweep

The last occurrence array turns each character into an interval from its first appearance in the active partition to its final appearance. The greedy scan keeps the union of those intervals and cuts as soon as the union closes.

Step-by-step

Fill an array last of size 26 so last[c] stores the final index of character c.
Sweep the string while maintaining the current partition start and required end.
For every character, extend end to the character's final index if needed.
When the scan reaches end, append the partition length and start a new partition at the next index.

Time

O(n)

Space

O(1)

The string is scanned twice and the last-occurrence array has 26 entries. The returned list is not counted as auxiliary space.

Java implementation

Loading…

Dry Run

Sample input

s = ababcbacadefegdehijhklij. Important last occurrences include a:8, b:5, c:7, d:14, e:15, f:11, g:13, h:19, i:22, j:23, k:20, l:21.

i	char	last[char]	partition start	current end after update	action
0	a	8	0	8	Extend first partition to index 8
1	b	5	0	8	Stay inside current boundary
2	a	8	0	8	Stay inside current boundary
3	b	5	0	8	Stay inside current boundary
4	c	7	0	8	Stay inside current boundary
5	b	5	0	8	Stay inside current boundary
6	a	8	0	8	Stay inside current boundary
7	c	7	0	8	Stay inside current boundary
8	a	8	0	8	Cut length 9
9	d	14	9	14	Start second partition
10	e	15	9	15	Extend second partition to index 15
11	f	11	9	15	Stay inside current boundary
12	e	15	9	15	Stay inside current boundary
13	g	13	9	15	Stay inside current boundary
14	d	14	9	15	Stay inside current boundary
15	e	15	9	15	Cut length 7
16	h	19	16	19	Start third partition
17	i	22	16	22	Extend third partition to index 22
18	j	23	16	23	Extend third partition to index 23
19	h	19	16	23	Stay inside current boundary
20	k	20	16	23	Stay inside current boundary
21	l	21	16	23	Stay inside current boundary
22	i	22	16	23	Stay inside current boundary
23	j	23	16	23	Cut length 8

The greedy cut points are indices 8, 15, and 23, producing partition lengths 9, 7, and 8.

Interview Tips

Start the explanation from the constraint each seen character creates: once a character appears, the current partition must include its last occurrence. Interviewers usually want to hear that cutting earlier is impossible and cutting later is wasteful, which is exactly the greedy-choice proof.

Likely follow-ups

How would the solution change if the alphabet were arbitrary Unicode characters?
Can you return the actual substrings instead of their lengths?
What if each character may appear in at most two partitions?
How would you stream the string if last occurrences were not known in advance?

Key Takeaways

A character's last occurrence is a hard boundary for the partition that first contains it.
The first valid cut is optimal because delaying it cannot create more partitions.
The running end represents the merged interval of all characters seen in the current partition.
Two linear scans are enough: one to learn future constraints and one to cut greedily.

Reusable template: Last-occurrence partitioning: precompute each symbol's final position, sweep while maintaining the farthest required boundary, and cut at the first index where all active symbols are contained.