Why it works
- A part that holds a letter has to reach that letter's last occurrence. So end, the farthest last occurrence of the letters seen in the part, is the shortest the part can be.
- When i reaches end, no letter of the part appears later, so cutting there is allowed. Cutting at the first such place leaves the most room for the parts after it, which gives the most parts.
- Like the reach on the card, end only grows inside a part, so one pass with one number is enough.
Complexity
Time O(n): one pass to find the last indices and one to cut. Memory O(1): the last index of at most 26 letters.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗