Approach #1: Greedy [Accepted]
Let's try to repeatedly choose the smallest left-justified partition.
Consider the first label, say it's
'a'. The first partition must include it, and also the last occurrence of
However, between those two occurrences of
'a', there could be other labels that make the minimum size of this partition bigger. For example, in
"abccaddbeffe", the minimum first partition is
This gives us the idea for the algorithm: For each letter encountered, process the last occurrence of that letter, extending the current partition
[anchor, j] appropriately.
We need an array
last[char] -> index of S where char occurs last.
j be the start and end of the current partition.
If we are at a label that occurs last at some index after
j, we'll extend the partition
j = last[c]. If we are at the end of the partition (
i == j) then we'll append a partition size to our answer, and set the start of our new partition to
Time Complexity: , where is the length of .
Space Complexity: .
Analysis written by: @awice.