Intervals & Greedy · 087Medium
Partition Labels
Given a string s, partition it into as many parts as possible so that each letter appears in at most one part. Return a list of the part sizes, in order. The parts concatenated in order must reconstruct s.
Constraints
- 1 <= s.length <= 500
- s consists of lowercase English letters.
Examples
partitionLabels("ababcbacadefegdehijhklij") -> [9, 7, 8]
partitionLabels("eccbbbbdec") -> [10]
partitionLabels("a") -> [1]
partitionLabels("aa") -> [2] // a repeat forces one part
partitionLabels("abc") -> [1, 1, 1] // all distinct, maximal split
partitionLabels("abab") -> [4] // interleaved letters cannot splitEdge cases
- A single character gives [1].
- One letter spanning the whole string forces a single part.
- The sizes must sum to s.length.
Show the target complexity (spoiler)
- Naive
- O(n^2) time — for each candidate cut, verify no letter straddles it.
- Target
- O(n) time, O(26) space — record each letter's LAST index, then sweep, closing a part when the cursor reaches the running maximum last-index.
Solve it
By hand, in your editor. The runner checks answers and timing.
git clone https://github.com/sarmadkung/optimal-round cd optimal-round # open problems/11-intervals-greedy/087-partition-labels.js ./practice c 087