Partition labels: cuts at last occurrences

Partition labels asks for a string to be cut into as many pieces as possible so that no letter appears in more than one piece, and for the sizes of the pieces. The greedy answer reads the string twice. First record the last position of every letter; then scan from the left, stretching the current piece to the last position of each letter met in it, and cut the moment the scan reaches the piece’s end. Every cut is safe because each letter seen so far is finished, and no possible cut is missed, so the pieces are as many as they can be: O(n) time and 26 counters of memory. Merging, for every letter, the range from its first to its last position gives the same pieces.

The problem: one rider per area

1. "mnmopqpqrssr" gives [3, 1, 4, 4]: the legs mnm, o, pqpq and rssr, as in the figure.
2. "abcd" gives [1, 1, 1, 1]: every stop is an area of its own.
3. "abca" gives [4]: the first and the last stop share an area, so the route cannot be cut at all.

The brute force, and why it fails at these sizes

For every place to cut, compare the set of areas on its left with the set on its right, and make every cut where the two share nothing:

# A courier's day: one letter per stop, the area code of the stop, in the order of delivery.
DAY = "mnmopqpqrssr"


def legs_by_checking_every_cut(route):
    """Checks every place to cut: a cut is allowed when no area code appears on both sides. Returns (sizes, letters read)."""
    read, cuts = 0, []
    for i in range(len(route) - 1):  # a cut between stop i and stop i + 1
        left, right = set(route[: i + 1]), set(route[i + 1 :])
        read += len(route)
        if not left & right:
            cuts.append(i)
    edges = [-1, *cuts, len(route) - 1]
    return [b - a for a, b in zip(edges, edges[1:])], read


print("the day", DAY, "->", legs_by_checking_every_cut(DAY))
print("abcd ->", legs_by_checking_every_cut("abcd"), "  abca ->", legs_by_checking_every_cut("abca"))
for n in (1_000, 2_000, 4_000):
    route = "".join("abcdefghij"[(i * 7) % 10] for i in range(n))
    print(f"{n:,} stops: {legs_by_checking_every_cut(route)[1]:,} letters read")

the day mnmopqpqrssr -> ([3, 1, 4, 4], 132)
abcd -> ([1, 1, 1, 1], 12)   abca -> ([4], 12)
1,000 stops: 999,000 letters read
2,000 stops: 3,998,000 letters read
4,000 stops: 15,996,000 letters read

Each cut reads the whole route once, so a route of n stops costs about n² letters read: 999,000 for 1,000 stops, 15,996,000 for 4,000 and about 10¹² for a million, which no time limit allows.

What to notice

• A cut after a stop is allowed exactly when every area seen so far has had its last stop. So the last stop of each area is the only fact about the rest of the route that matters.
• Allowed cuts never get in each other’s way. Making one does not stop another, so the most legs come from making every allowed cut.

The scan with a last-stop table, step by step Pro: opens with a Pro, Premium or Ultimate pass