Pattern Recognition Drill
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.
Track last occurrence of each char. Extend current partition to max(last[c]). When i == end, cut. O(n).
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.