Greedy
Deciding where a group ends
Look ahead once, then walk forward and let the lookahead tell you when you may stop.
Key idea
Groups that cannot be split
Cut a sequence into as many pieces as possible, subject to a rule that certain elements must end up in the same piece. Concretely: every occurrence of a character must be in one piece.
That means a piece cannot end before the last occurrence of anything it contains. Once that sentence is written, the algorithm follows.
Why it works
One pass to look ahead, one to sweep
First pass: record the last position of each element. That is the lookahead and it costs one scan.
Second pass: walk forward keeping the furthest last-position seen so far. When the current position equals that furthest, nothing inside the current piece extends beyond here, so the piece can close.
That closing condition is the whole algorithm, and it is the same running-maximum shape as the reachability lesson with a different meaning attached.
The lookahead map is the first pass, and it is worth printing on its own before thinking about the sweep.
Tip
The dict comprehension keeps the last index
Building the map by iterating forward means later positions overwrite earlier ones, so each key ends up holding the final occurrence. That is exactly what is wanted and needs no explicit maximum.
It is the opposite of the first-occurrence map from Unit 1's balanced-subarray debrief, where overwriting was the bug. Same construction, opposite intent, and worth being deliberate about which one a problem needs.
Why it works
Why closing as early as possible is optimal
To maximize the number of pieces, each piece should be as short as legally possible. Closing at the first position where the constraint permits is therefore forced, not merely preferable.
Extending a piece past that point cannot create more pieces later, because everything after it was already available. This is the forced-choice argument again rather than an exchange.
Key idea
The same shape elsewhere
Precompute a constraint, then sweep while maintaining the furthest obligation, is a reusable pattern. It covers grouping problems, interval-covering problems, and scheduling where a job blocks a window ahead of it.
The two components are always the same: something computed by looking ahead, and a running maximum of pending obligations. Naming them separately makes the sweep obvious.
Cost
Cost
Two linear passes, so O(n) time. The map holds one entry per distinct element, which is O(1) for a fixed alphabet and O(n) in general.
Saying which of those two the problem's constraints imply is a small precision that is worth making.
Find the reset bug
This splits a permutation of 0 through n-1 into the largest chunks that can each be sorted on their own. Every size after the first comes out too large. Click the line that is wrong.
This activity type is not wired up yet.
Partition Labels
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.