The Partition Labels problem asks you to partition a string into as many parts as possible such that each character appears in at most one part. Return the sizes of each part. This coding problem uses a greedy approach based on the last occurrence of each character. The hash table, two pointers, string, and greedy interview pattern is the core.
Microsoft, Meta, Amazon, LinkedIn, Google, and Bloomberg ask this because it tests the greedy insight of extending the current partition to include all characters that have appeared in it. The "last occurrence" precomputation is key.
Last occurrence + greedy scan. Precompute last[c] = last index of character c in the string. Scan left to right: maintain end = farthest last occurrence of any character in the current partition. When i == end, the current partition is complete (add size, reset start). Update end = max(end, last[s[i]]) at each step.
s="ababcbacadefegdehijhklij". last: a=8,b=5,c=7,d=14,e=15,f=11,g=13,h=19,i=22,j=23,k=20,l=21.
Partition Labels is a beautiful greedy problem. The insight: a partition can end only when all characters within it have been "fully contained" — no character extends beyond the current boundary. The greedy approach naturally finds the minimum number of characters that must be in each group. Practice similar "expand partition to include all occurrences" problems — they all use the same last-occurrence greedy sweep.
