Partition Labels

Medium

Extend the part to each letter's last index

Problem

Partition a string into as many parts as possible so each letter appears in at most one part. Return the sizes of the parts.

In simple words

Extend the current part to the last position of any letter it contains, then cut when you reach that end.

The idea

Record the last index of every character, then sweep extending the current partition's end to cover the last occurrence of each letter you meet. When the sweep index reaches that end, every letter inside is fully contained and the part can close.

The trick

One pass to record last indices, one to cut.
Close the part when `i == currentEnd`.
O(n) time, O(alphabet) space.

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

←→stepspaceplay

1/2

Optimal

timeO(n)spaceO(1)

1last[c]=last index of c2start=end=03for i,c in s:4  end=max(end,last[c])5  if i==end: record size i-start+1; start=i+1

Input

array: [0]

Output

answer: —

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:: s = "ababcbacadefegdehijhklij"
Output:: [9, 7, 8]
Explanation:: Cut where every letter seen so far is finished → [9,7,8].

Example 2

Input:: s = "eccbbbbdec"
Output:: [10]
Explanation:: One big part → [10].

Example 3

Input:: s = "abc"
Output:: [1, 1, 1]
Explanation:: Each letter is its own part → [1,1,1].

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.