Try to come up with a greedy approach.

From left to right, extend every substring in the partition as much as possible.