Split a string into as many parts as possible, so each letter appears in at most one part. Return the sizes of the parts.
DSA Animator › DSA Revision › Greedy › Partition Labels
Remember: a part cannot close before the last copy of every letter inside it. Stretch the end, and cut when you reach it. The video solves Partition Labels (LeetCode 763, Medium) with the Greedy Last Occurrence pattern from the Greedy topic, and you can replay every step in the interactive Partition Labels animation.
Split a string into as many parts as possible, so each letter appears in at most one part. Return the sizes of the parts.
For a, b, a, c, d, c, d, e, f, e, the parts are a b a, then c d c d, then e f e. The sizes are 3, 4 and 3.
Trying every way to cut the string is exponential. What matters is where each letter appears for the last time.
First record the last index of every letter. Scan the string, and stretch the current end to the last index of each letter you see. When i reaches the end, close the part and start a new one.
The last indexes are a at 2, b at 1, c at 5, d at 6, e at 9 and f at 8. At index 0, a pushes the end to 2, and at index 2 we reach it, so the first part has size 3. c pushes the end to 5, then d pushes it to 6, and at index 6 the second part closes with size 4. e pushes the end to 9, f stays inside, and at index 9 the last part has size 3. The answer is 3, 4, 3.
In code, one loop fills the last index for each letter. A second loop updates end with the maximum last index. When i equals end, add end minus start plus 1, and move start. It's O of n time and O of 1 space for 26 letters.
Remember: a part cannot close before the last copy of every letter inside it. Stretch the end, and cut when you reach it.