Medium · Last Occurrence Greedy
Understand → Visualise → Practice.
Split text into as many parts as possible so each character occurs in only one part; return part lengths.
A part must reach at least to the last occurrence of every character in it. Scan, stretching the current part's end, and cut whenever you reach that end.
Store the last index of every character.
Scan left to right with end = max(end, last[ch]).
When the index equals end, record the part's length and start a new part.
O(n) time and O(1) space for a fixed alphabet.
Cutting when you first see a repeated character is too early: later letters in the part may reach further.
Read the full guide first: Greedy Algorithms and Interval Patterns.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.