Partition labels with last occurrences in Python

Why this matters

Many tasks cut a long sequence into pieces that can each be handled alone. A text editor splits a document into pages. A log tool splits a stream of events into batches. In each case you want as many pieces as possible, and no item may show up in two pieces.

This lesson solves a small puzzle of that kind. You get a string of lowercase letters. You cut it into parts, in order, so that each letter appears in only one part. You want as many parts as you can get. The answer is the length of each part.

For the string ababcbacadefegdehijhklij the answer is 9, 7, 8. The first part is ababcbaca. It holds every a, b and c in the string, so no other part can use those letters. The second part is defegde, and the third is hijhklij.

The solution is greedy. A greedy method makes the choice that looks best at each step, and never goes back to change it. Here the step is simple: cut as soon as a cut is safe. The lesson shows how to tell when a cut is safe, and why cutting at every safe point gives the most parts. The method needs one list of 26 numbers and two passes over the string.

The merge intervals lesson earlier in this module also sorts and scans a list, but its input is a list of ranges, not a string. This lesson does not repeat it.

Words you need

An index is the position of a character in a string. Python counts from 0, so the first character is at index 0, and the last character of a string of length n is at index n - 1.

A part is a piece of the string made of characters that sit next to each other. A cut is the place between two characters where a part ends and the next part starts.

The last occurrence of a letter is the largest index where that letter appears. In abacbc, the letter a appears at indexes 0 and 2, so its last occurrence is 2.

A cut is safe when no letter appears on both sides of it. If you cut abacbc after index 1, the left side is ab and the right side is acbc. The letter a is on both sides, so that cut is not safe. Cutting after index 2 gives aba and cbc. The letter b is on both sides, so that cut is not safe either.

The idea in plain words

Start with a short string, ababcc. Write each character with its index under it:

index:  0 1 2 3 4 5
letter: a b a b c c

The last occurrences are: a at 2, b at 3, and c at 5.

Now read the string from left to right. Keep a number called reach. It is the furthest index that the current part must include. Every letter you read pushes reach out to that letter's last occurrence, if the letter ends later than the current reach.

1. Index 0 is a. Its last occurrence is 2, so the part must reach at least index 2. reach is 2.
2. Index 1 is b. Its last occurrence is 3. reach becomes 3.
3. Index 2 is a. Its last occurrence is 2, which is less than 3. reach stays 3.
4. Index 3 is b. Its last occurrence is 3. You are now at index 3, and reach is 3. Every letter seen in this part has already ended. This is a safe cut. The first part is indexes 0 to 3, which is abab. Its length is 4.
5. Index 4 is c. Its last occurrence is 5. reach becomes 5.
6. Index 5 is c. You are at index 5, and reach is 5. Cut. The second part is indexes 4 to 5, which is cc. Its length is 2.

The answer is 4, 2. The two parts share no letter.

The rule to remember is this: when the scan index equals reach, the current part is complete, so cut after this index.

Why cutting at every safe point is best

A safe cut stays safe no matter what else you do. Cutting the string never adds a letter to a part, so a cut that split letters cleanly before still splits them cleanly after any other cut. That means a best answer should use every safe cut. Taking one more safe cut can only add a part, never break the rule.

The scan finds every safe cut. After each safe cut, the next part starts fresh, and the letters in earlier parts never come back. So the only letters that can keep a cut from being safe are the ones inside the current part. The scan tracks exactly those letters with reach. When reach equals the current index, no letter in the part reaches past it, so the cut is safe. When reach is larger, some letter still continues further, so the cut is not safe. The scan never misses a safe point and never takes an unsafe one.

This is why the method is greedy and still correct. Each choice is the locally best one, and the choices never need to be undone.

Step 1: record the last index of each letter

The first pass walks the whole string once and writes down the index of each letter. Each time a letter appears, its entry is overwritten with the newer index. When the pass ends, each entry holds the last index of that letter.

last = [0] * 26
for i, ch in enumerate(s):
    last[ord(ch) - ord("a")] = i

[0] * 26 makes a list of 26 zeros, one slot for each lowercase letter. The function ord(ch) gives the code number of the character ch. The letter a has the code 97 and b has 98. Subtracting ord("a") turns a into 0, b into 1, and z into 25. That number is the slot for the letter.

Python has no separate character type. A character is a string of length 1, so ch here is a one-letter string.

The slot number is enough to find the letter's entry, so no separate table of letter names is needed.

Step 2: scan and cut

The second pass uses the list from step 1. It keeps two numbers: start, the index where the current part begins, and reach, the furthest index the current part must include. The max function is built into Python, so the function needs no import line.

The line reach = max(reach, last[...]) is the heart of the method. It takes the larger of the two numbers, so reach never goes down. Inside one part, reach only grows.

When i == reach, the part is complete. Its length is reach - start + 1. The + 1 is needed because both ends are included. A part from index 4 to index 5 has length 5 - 4 + 1 = 2. After the cut, start moves to i + 1, the first index of the next part.

The four calls at the bottom of the block print these results:

[6]
[4, 2]
[9, 7, 8]
[6, 2]

The first answer is [6] because abacbc is one part. Every cut inside it is unsafe. Here is the check. The letter a ends at index 2, b ends at index 4, and c ends at index 5. The first cut that could be safe is after index 5, which is the end of the string.

Worked example 1: a string with three parts

Take the string from the start of the lesson, ababcbacadefegdehijhklij. It has 24 characters, so the indexes run from 0 to 23. The last occurrences are: a at 8, b at 5, c at 7, d at 14, e at 15, f at 11, g at 13, h at 19, i at 22, j at 23, k at 20, and l at 21.

Here is the first part, from index 0 to index 8. The table shows the values at some of the steps. The value of reach only changes when the new letter ends later than before.

At index 0, the letter a ends at 8, so reach becomes 8. The letters b and c end before 8, so reach stays 8 all the way through. At index 8 the scan reaches reach, and the first part is indexes 0 to 8, which is ababcbaca. Its length is 9.

The second part starts at index 9. The letter d at index 9 ends at 14, so reach becomes 14. The letter e at index 10 ends at 15, so reach becomes 15. The scan continues. The letter f at 11 ends at 11, and g at 13 ends at 13, so neither changes reach. At index 15 the scan reaches reach. The second part is indexes 9 to 15, which is defegde. Its length is 15 - 9 + 1 = 7.

The third part starts at index 16. It goes to index 23, the end of the string, because j at index 23 is its last occurrence. The part is hijhklij, with length 8. The three lengths are 9, 7 and 8, so the answer is [9, 7, 8].

The method found three cuts without ever comparing two letters directly. It only looked at the last index of each letter.

Worked example 2: a chain of overlaps

Some strings have no safe cut for a long stretch, then one arrives. Take abcabcdd. The letters a, b and c each appear twice in the first six characters. The letter d appears twice at the end.

Here are the last occurrences: a at 3, b at 4, c at 5, and d at 7.

Start at index 0. The letter a ends at 3, so reach is 3. Index 1 is b, which ends at 4, so reach is 4. Index 2 is c, which ends at 5, so reach is 5. From here on, no letter ends later than 5 inside the first six characters, so reach stays 5. The scan reaches index 5, and it cuts. The first part is abcabc, with length 6.

The next part starts at index 6. Both characters are d, and the last d is at index 7. The scan cuts at index 7, giving the part dd with length 2.

The answer is [6, 2], which is the output shown above. The lesson here is that reach can rise through many letters, one step at a time, before the cut comes. The scan does not need to know the chain in advance. It only needs reach to be the largest index seen so far in the current part.

Worked example 3: a string with a single letter in each part

A harder test is a string where each part has a letter that ends in the middle of another part. Take xyzzy. The last occurrences are x at 0, y at 4, and z at 3.

Index 0 is x, which ends at 0. The scan is at index 0 and reach is 0, so the first part is x, with length 1.

Index 1 is y, which ends at 4. reach becomes 4. Index 2 is z, which ends at 3, so reach stays 4. Index 3 is z, which also ends at 3, so reach stays 4. Index 4 is y, and the scan reaches reach. The second part is yzzy, with length 4.

The answer is [1, 4]. The z letters are inside the second part, and the y letters are at both ends of it. The scan did not need to check the z letters separately. The large last index of y was enough to keep the part together.

Common mistakes

The most common mistake is to cut at the last occurrence of the letter the scan is on. A learner might write this:

reach = last[ord(ch) - ord("a")]

This replaces reach with the last index of the current letter. It does not keep the furthest index seen so far. Here is the whole function with that one line changed, run on abacbc:

The real output is:

[3, 2, 1]
[6, 2, 1, 3, 2, 1, 1, 4, 1, 1, 1, 1]

The first answer is wrong. The parts are aba, cb and c. The letter c appears in the second part and again in the third part, so the rule is broken. The output looks like a valid answer because the three numbers add up to 6, the length of the string. The second answer also adds up, to 24, and it also breaks the rule, so a quick check of the sum does not find the bug.

The fix is the line reach = max(reach, ...). The max keeps the largest index the part has seen.

A second mistake is forgetting the + 1 in the length. Look at a part that is a single letter, such as x in xyzzy. Its start and its reach are both 0. The expression reach - start gives 0, not 1. A part of length 0 is not a part, so the answer is wrong. The fix is reach - start + 1.

A third mistake is looking at the wrong slot. The slot for a letter is ord(ch) - ord("a"). If you write last[ord(ch)] without the subtraction, Python uses the character's code number, which is 97 for a. The list has only 26 slots, so Python stops with an error:

last = [0] * 26
last[ord("a")] = 1

The real output is below. The folder part of the file path is left out.

Traceback (most recent call last):
  File "slot_bug.py", line 2, in <module>
    last[ord("a")] = 1
    ~~~~^^^^^^^^^^
IndexError: list assignment index out of range

The last line gives the error type and the message. Subtract ord("a") to get a slot between 0 and 25.

A fourth mistake happens with strings that contain uppercase letters or digits. The subtraction gives negative numbers for them. For example ord("A") - ord("a") is -32. A list accepts a negative position and counts it from the end, so position -1 is the last slot, -2 is the one before it, and so on. Only positions from -26 to -1 are real slots for a list of 26. Some of the bad numbers fall in that range, and then Python does not stop. It writes to the wrong slot. The letter t has the code 116, so ord("t") - ord("a") is 19. The letter Z has the code 90, so ord("Z") - ord("a") is -7, and -7 is the same slot as 19:

print(partition_labels("Zta"))

[2, 1]

The three characters Z, t and a are three different letters, so the correct answer is [1, 1, 1]. The output [2, 1] is wrong, and Python gave no error. The code treated Z and t as the same letter. The exercise below shows a version that handles any characters.

A character such as A or 1 gives a different result. Its number is so far below the slot range that Python does stop:

IndexError: list assignment index out of range

Practice

Exercise 1. Trace aaabbbcc by hand. Write down the last index of each letter, then the value of reach at each index, and list the lengths of the parts.

Show the answer

The last indexes are a at 2, b at 5, and c at 7. The scan cuts at index 2 (part aaa, length 3), at index 5 (part bbb, length 3), and at index 7 (part cc, length 2). The answer is [3, 3, 2].

Exercise 2. Trace zzyx by hand. What are the lengths of the parts?

Show the answer

The last indexes are z at 1, y at 2, and x at 3. Index 0 is z, and reach becomes 1. Index 1 is z, and the scan cuts there, giving zz with length 2. Index 2 is y, which ends at 2, so it is a part of length 1. Index 3 is x, also length 1. The answer is [2, 1, 1].

Exercise 3. Explain in your own words why cutting at i == last[c] fails on abacbc. Use the output [3, 2, 1] and name the letter that breaks the rule.

Show the answer

The rule cuts after the first index where the current letter ends, and it does not look at letters that end later. In abacbc, index 2 is the second a, so the first part is aba. But the b at index 4 is still to come. The second part cb holds that second b, while the first part aba already holds the first b. So the letter b is in two parts, and the letter c is in two parts too (cb and c). The check is to compare each part with the rule: no letter may appear in two parts.

Exercise 4. Change partition_labels so it works for any characters, not only lowercase letters. Use a dict from each character to its last index. Run it on A1a1 and on ababa.

Show the answer

Use a dict in place of the list. In the first pass, store last[ch] = i. In the second pass, read last[ch]. The code is:

The real output is [1, 3] for A1a1, and [5] for ababa. The A is alone, then 1a1 is one part, because the digit 1 appears at index 1 and index 3. A dict has no slot numbers to compute, so it works for any character.

Exercise 5. Without running code, predict the output for abcabcdd and xyzzy. Then check your answer by running the program.

Show the answer

The output for abcabcdd is [6, 2], and for xyzzy it is [1, 4]. These are the same results worked out in the examples above.

Summary

• A cut is safe when no letter appears on both sides of it.
• Record the last index of each letter in one pass, using a list of 26 slots for lowercase letters, or a dict for any characters.
• In the second pass, keep reach as the largest last index seen in the current part, and cut when the scan index equals reach.
• Use max when updating reach. Plain assignment gives a wrong answer that can still add up to the length of the string.
• The length of each part is reach - start + 1.
• Taking every safe cut gives the most parts, so the greedy choice is correct.