Pattern Recognition Drill
Medium Greedy
The Problem
Partition string into most parts so each letter appears in at most one part.
What approach would you use?
Think about it before scrolling down.
Map each char to its last index. Scan: extend partition end to max(last[c]). Cut when i == end. O(n).
The hash map is part of the greedy solution — used to precompute last occurrences.
Common Trap
This is an interval merging problem in disguise. Each character defines an interval [first, last].