First pass: record the last index of each character. Second pass: maintain the end of the current partition. Start at index . For each character, extend the partition end to that character's last occurrence.
When you reach the partition end, you have found a valid cut. The greedy choice: extend as little as needed.
You must include all occurrences of each character, so extend to the farthest last occurrence seen so far. Time: . Space: .