Partition Labels
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]
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;}