Subsequence Automaton (Next-Occurrence Table)

This is an extension topic beyond most interviews; it pays off in the classic follow-up "now check millions of candidate subsequences against the same long string", and in a few hard counting problems about subsequences.

Intuition

To test whether t is a subsequence of s, the greedy rule is optimal: match each character of t at its earliest possible position in s. Taking a later occurrence never helps, because the remaining suffix of s would only be shorter.

So the only question we ever ask is "starting from index i, where does character c occur next?". Precompute the answer for every i and every c:

nxt[i][c] = the smallest j >= i with s[j] == c, or n if there is none.

Build it from right to left: row i is row i + 1 with the entry for s[i] replaced by i. This table is a tiny automaton with n + 1 states (state i means "the next usable index is i"), and every path from state 0 spells a distinct subsequence, matched greedily. That one fact gives both fast queries and counting DPs.

For a large alphabet or tight memory, store each character's position list instead and binary-search for the first position >= i.

When to use it in interviews / OAs

• "Is subsequence" with many queries against one string (the well-known follow-up), or "number of matching subsequences" for a list of words.
• "Minimum number of copies of source whose concatenation contains target as a subsequence" (shortest way to form a string).
• "Shortest string (or roll sequence) that is not a subsequence of s."
• "Count distinct subsequences" (modulo a prime).

Template

The table and greedy matching

from bisect import bisect_left

LOWER = "abcdefghijklmnopqrstuvwxyz"


class SubsequenceAutomaton:
    def __init__(self, s: str, alphabet: str = LOWER):
        self.n = len(s)
        self.idx = {c: k for k, c in enumerate(alphabet)}
        self.nxt = [[self.n] * len(alphabet) for _ in range(self.n + 1)]  # n = "no more"
        for i in range(self.n - 1, -1, -1):
            row = self.nxt[i + 1][:]
            row[self.idx[s[i]]] = i
            self.nxt[i] = row

    def match_end(self, t: str, start: int = 0) -> int:
        # greedily match t inside s[start:]; index after the last matched character, or -1
        i = start
        for ch in t:
            k = self.idx.get(ch)
            if k is None or self.nxt[i][k] == self.n:
                return -1
            i = self.nxt[i][k] + 1
        return i

    def is_subsequence(self, t: str) -> bool:
        return self.match_end(t) != -1

Memory-light version with binary search

class PositionListMatcher:
    def __init__(self, s: str):
        self.pos: dict[str, list[int]] = {}
        for i, ch in enumerate(s):
            self.pos.setdefault(ch, []).append(i)

    def is_subsequence(self, t: str) -> bool:
        i = 0  # first index of s that may still be used
        for ch in t:
            lst = self.pos.get(ch, [])
            k = bisect_left(lst, i)  # first occurrence at or after i
            if k == len(lst):
                return False
            i = lst[k] + 1
        return True

Problems built on the table

def shortest_way_to_form(source: str, target: str) -> int:
    # fewest copies of source whose concatenation has target as a subsequence
    if not target:
        return 0
    auto = SubsequenceAutomaton(source)
    copies, i = 1, 0
    for ch in target:
        k = auto.idx[ch]
        if auto.nxt[0][k] == auto.n:
            return -1  # ch never appears in source
        if auto.nxt[i][k] == auto.n:  # not in the rest of this copy: start a new one
            copies += 1
            i = 0
        i = auto.nxt[i][k] + 1
    return copies


def shortest_non_subsequence_len(s: str, alphabet: str) -> int:
    # length of the shortest string over alphabet that is NOT a subsequence of s
    auto = SubsequenceAutomaton(s, alphabet)
    n = auto.n
    f = [1] * (n + 1)  # f[i]: answer for the suffix s[i:]; any single letter beats the empty suffix
    for i in range(n - 1, -1, -1):
        f[i] = 1 + min(0 if j == n else f[j + 1] for j in auto.nxt[i])
    return f[0]


def count_distinct_subsequences(s: str, mod: int = 10**9 + 7) -> int:
    # non-empty distinct subsequences = paths from state 0, minus the empty one
    auto = SubsequenceAutomaton(s)
    n = auto.n
    g = [1] * (n + 1)  # g[i]: distinct subsequences of s[i:], including the empty one
    for i in range(n - 1, -1, -1):
        g[i] = (1 + sum(g[j + 1] for j in auto.nxt[i] if j < n)) % mod
    return (g[0] - 1) % mod

Complexity

• Table: O(n * A) time and memory for alphabet size A (26 for lowercase); each query O(len(t)).
• Position lists: O(n) to build and store; each query O(len(t) log n).
• The two DPs: O(n * A).

For n = 10^5 and 26 letters the table holds 2.6 million integers, a few tens of megabytes in Python; if that is too much, use the position lists.

Common pitfalls

• Not greedy. Matching a character at a later position than necessary can only lose; always take the earliest.
• Off-by-one after a match. After using index j, continue from j + 1, not j.
• The sentinel. n means "does not occur"; it is a valid state index (the empty suffix), so check for it before using nxt[n] as a match.
• Characters outside the alphabet (uppercase, digits): either size the alphabet for them or fail fast, as match_end does.
• Rebuilding per query. The table is built once; the whole point is that queries are cheap.
• Counting duplicates. The DP counts distinct subsequences because each one has exactly one greedy path; counting by positions (all index choices) is a different DP.

Interview variations

• Is subsequence (follow-up with many queries). Build once, then is_subsequence(t) per query.
• Number of matching subsequences. Sum of is_subsequence(w); an alternative is to bucket words by the next character they wait for and scan s once.
• Shortest way to form a string. shortest_way_to_form above.
• Shortest impossible sequence of rolls. Same as shortest_non_subsequence_len; there is also a neat greedy: count how many times a full set of symbols completes while scanning, plus one.
• Distinct subsequences. The path-counting DP; the classic alternative tracks the last occurrence of each character.
• Longest word in a dictionary that is a subsequence of s. Sort candidates by (length descending, lexicographic) and test each with the table.