Blends off the blotter

A perfumer lays a strip of dabs in a fixed order and reads blends off it. Two different handfuls of dabs can spell the same blend, and the house counts blends.

The problem

The blotter carries a row of dabs, each a single note written as one letter — r rose, j jasmine, c cedar, v vetiver. The order on the strip is fixed.

A blend is made by choosing at least one dab and reading the chosen notes off in strip order. Two blends are the same blend when they read the same: on the strip r j r the first and third dabs both read as r, so those two choices are one blend, not two.

Count the distinct blends the strip can produce, modulo 1,000,000,007.

Input. dabs — a non-empty string of lowercase letters, the notes in strip order.

Output. The number of distinct non-empty readings, modulo 10⁹ + 7.

Example.

dabs = "rjc"   ->  7

All three notes differ, so every non-empty choice reads differently: r, j, c, rj, rc, jc, rjc.

A second example, where a repeat collapses two choices into one:

dabs = "rjr"   ->  6

Seven choices, but dab 1 and dab 3 both read as r. Everything else is distinct: r, j, rj, rr, jr, rjr.

A third example, all one note:

dabs = "rrr"   ->  3

Only the length survives: r, rr, rrr.

Constraints.

• 1 <= len(dabs) <= 2 * 10^5
• every character is a lowercase letter
• report the count modulo 1,000,000,007

Hints

Approach

Brute force

List every choice of dabs, read each off, and drop repeats with a set: 2ⁿ readings built and stored. Twenty dabs is a million strings; the strip holds two hundred thousand.

The insight

Group the blends by their last note: dabbing a note replaces that group with "every blend so far, extended by this dab, plus the dab alone", and the replacement is exactly where the duplicates go.

A blend ending in r is some earlier blend, or nothing at all, with an r on the end. When a new r arrives, every reading that ended at an older r can be made again by ending at this one, so the new group contains the old rather than adding to it. That keeps the count exact: each reading is counted once, in the group of its final note — twenty-six numbers, whatever the strip's length.

Algorithm

1. Keep total, the distinct blends so far, and ending[note] for each note, all starting at zero.
2. For each dab of note c, compute fresh = total + 1 — every blend so far extended by this dab, plus the dab on its own.
3. Set total = total - ending[c] + fresh; the old group for c is superseded.
4. Set ending[c] = fresh.
5. Return total modulo 10⁹ + 7.

Complexity

Time O(n) — one dab, a fixed amount of arithmetic. Space O(k) for the alphabet: twenty-six counters plus the running total, independent of the strip.

Solution

"""Blends off the blotter — count the distinct orders a strip of notes can yield."""

MOD = 10 ** 9 + 7


def solve(dabs):
    total = 0        # distinct non-empty blends from the strip read so far
    ending = {}      # ending[note] = how many of those finish on that note

    for note in dabs:
        # every blend so far, extended by this dab, plus the dab on its own;
        # those are exactly the blends ending on this note now, so the old
        # count for the note is replaced rather than added to
        fresh = (total + 1) % MOD
        total = (total - ending.get(note, 0) + fresh) % MOD
        ending[note] = fresh
    return total

TESTS = [
    (("rjc",), 7),
    (("rjr",), 6),
    (("rrr",), 3),
    (("jcvr",), 15),
    (("abcdefghijklmnopqrstuvwxyz",), 67108863),
    (("ab" * 100,), 407981058),
    (("v",), 1),
]

Pitfalls

• Answering 2ⁿ − 1. That counts choices of dabs, not readings; with a repeated note it overshoots — rrr gives 7 that way and 3 in truth.
• Adding rather than replacing. total += fresh counts every blend ending on a repeated note twice, turning rjr into 7.
• Reducing before subtracting. Once both are taken modulo 10⁹ + 7, total - ending[c] can come out negative; add the modulus back before reporting, in any language whose % follows the sign of the left side.

Variants

• Two hydrophones — subsequences again, matched against a second sequence instead of counted.
• Burns and vents — another counting DP whose state is what has been reached, not which choices got there.