Pattern Recognition Drill

#149 — Partition Labels

Medium Greedy

The Problem

Partition a string so each letter appears in at most one part. Maximize the number of parts.

What approach would you use?

Think about it before scrolling down.

Key Signals

'Each letter in at most one part' → partition must extend to last occurrence of each letter
'Maximize parts' → greedily make each part as small as possible

Greedy

Track last occurrence of each char. Extend current partition to max(last[c]). When i == end, cut. O(n).

Alt: Hash Map

Same. The hash map of last occurrences is the key data structure.

Common Trap

Don't try to split greedily without precomputing last occurrences — you'd need to scan ahead repeatedly.

← #148