partition labels [M]

the problem

You are given a string s consisting of lowercase english letters. We want to split the string into as many substrings as possible, while ensuring that each letter appears in at most one substring. Return a list of integers representing the size of these substrings in the order they appear in the string.

We are given the following example:

Input: s = "xyxxyzbzbbisl"

Output: [5, 5, 1, 1, 1]
[xyxxy][zbzbb][i][s][l]

the idea

We can use the two pointers technique to solve this. If we can figure out every point where there are no more letters of certain kind after that point, we should be able to figure out where to make our cuts.

the solution

We start by marking the last occurrence of every single character. This can be achieved using a dictionary.

lastIndex = {}
for i, c in enumerate(s):
	lastIndex[c] = i

With this dictionary setup, we can start figuring out our partitions. Here is where our two pointers come in handy. Pointer 1 is set at the beginning of the list. We walk through the string, noting every single character and the location of its final occurrence. We walk all the way to the furthest final occurrence, and make our cut. Rinse and repeat until the entire string is covered.

cuts = []
start = end = 0

for i, c in enumerate(s):
    end = max(end, last[c])  # make sure we include the furthest partition
    if i == end:  # partition is complete
        cuts.append(end - start + 1)
        start = i + 1

return cuts