Partition Labels
Medium· Last Occurrence
Problem
Split a lowercase string into as many contiguous parts as possible such that each letter appears in at most one part. Return the lengths of the parts in order.
Examples
Input: s = "ababcbacadefegdehijhklij"
Output: [9,7,8]
The parts are "ababcbaca", "defegde" and "hijhklij".
Input: s = "eccbbbbdec"
Output: [10]
Constraints
- • 1 <= s.length <= 500
- • s consists of lowercase English letters
Hints & approach
Hint 1
A part that contains a letter must extend at least to that letter's last occurrence.
Hint 2
Record the last index of every letter first.
Hint 3
Grow the current part's end as you scan; when your index reaches the end, cut.
Approachtry the hints first
Precompute last[c], the final index of each letter. Scan with a part start and a running end; at index i, set end = max(end, last[s[i]]). When i equals end, every letter seen in this part is fully contained, so record end - start + 1 and start a new part at i + 1. Cutting at the earliest possible point maximizes the number of parts.
Time O(n) · Space O(1)