Partition Labels
Medium · Greedy
You are given a string of lowercase letters. Split it into as many consecutive pieces as possible so that each letter of the alphabet appears in only one piece (every occurrence of a given letter must stay inside the same piece). Return the lengths of the pieces in the order they occur.
Examples
Input: s = "ababcbacadefegdehijhklij"
Output: [9, 7, 8]
Why: The letters a,b,c cluster together needing 9 characters before they never reappear, then d,e,f,g need 7 more, then h,i,j,k,l fill the last 8.Input: s = "eccbbbbdec"
Output: [10]
Why: Letter e first appears at index 0 and last appears at index 9, so no split can happen before the whole string ends.Input: s = "abac"
Output: [3, 1]
Why: a and b are both confined to the first 3 characters (a last appears at index 2), then c stands alone.Constraints
1 <= len(s) <= 5 * 10^5, s consists of lowercase English letters only
Practise it by voice
Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.
This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Partition Labels. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.