Partition Labels

Medium

Problem

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

Example 1

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

"ababcbaca", "defegde", "hijhklij".

Test cases

Case 1

Input:    "ababcbacadefegdehijhklij"
Expected: [9,7,8]

Case 2

Input:    "eccbbbbdec"
Expected: [10]

Case 3

Input:    "abc"
Expected: [1,1,1]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Last occurrence + extend the cut

Time O(n)Space O(26)

Record each char’s last index. Walk the string, extending the current part’s end to the last index of every char seen; cut when i reaches it.

function partitionLabels(s) {
const last = {};
for (let i = 0; i < s.length; i++) last[s[i]] = i;
const res = [];
let start = 0, end = 0;
for (let i = 0; i < s.length; i++) {
end = Math.max(end, last[s[i]]);
if (i === end) { res.push(end - start + 1); start = i + 1; }
}
return res;
}