Interleavings and distinct subsequences

Two classic string tables share one idea: a pair of positions. The interleaving string problem asks whether a string c is a merge of two strings a and b that keeps the order of each; the interleavings of two queues of announcements into one broadcast are exactly such merges. The distinct subsequences problem asks how many different sets of positions in a long string spell a short one, such as an error code in a log. Both brute forces branch at every letter, and both become tables of (n + 1)(m + 1) cells: true or false for interleavings, a count for distinct subsequences.

Two problems: a merged broadcast and a code in a log

Problem A: an interleaving string. A station keeps two queues of announcements, a and b, written as strings of codes, and one broadcast c. Return whether c is an interleaving of a and b: every letter of both queues appears in c exactly once, and each queue’s letters keep their order. Limits: each queue has 0 to 1,000 letters.

• a = "PQR", b = "XY", c = "PXQYR": true.
• c = "PYXQR": false, Y comes before X.
• c = "PXQY": false, R is missing.

Problem B: distinct subsequences. Count the ways the code t occurs in the log s as a subsequence, as different sets of positions, modulo 1,000,000,007. Limits: up to 10,000 log letters and 100 code letters.

• "ERR" in "ERRORERROR": 18 ways.
• "OK" in "OKERRKOERR": 2 ways.

The brute force, and why it fails at these sizes

For Problem A, take the next letter of c from a if it fits and solve the rest; if that fails, take it from b. When the queues share letters both branches can live for a long time: with 20 letters that are all equal except the last, the search makes 520,675 calls before it answers false, about 15 times more for every 4 more letters. For Problem B, try every set of positions: a code of 3 letters in a log of 10,000 letters gives 166,616,670,000 sets.

# Both problems by brute force. Interleaving: at each letter of the broadcast, try taking it from the first queue and,
# failing that, from the second. Counting: try every set of positions in the log. The work is counted.
from itertools import combinations
from math import comb


def interleaves(a, b, c, i=0, j=0, calls=None):
    """Is c[i + j:] an interleaving of a[i:] and b[j:]?"""
    calls[0] += 1
    if i + j == len(c):
        return i == len(a) and j == len(b)
    take_a = i < len(a) and a[i] == c[i + j] and interleaves(a, b, c, i + 1, j, calls)
    return take_a or (j < len(b) and b[j] == c[i + j] and interleaves(a, b, c, i, j + 1, calls))


def count_ways(log, code):
    """(ways, position sets tried): every choice of len(code) positions of the log is read and compared."""
    tried = ways = 0
    for picks in combinations(range(len(log)), len(code)):
        tried += 1
        ways += all(log[p] == ch for p, ch in zip(picks, code))
    return ways, tried


for a, b, c in [("PQR", "XY", "PXQYR"), ("PQR", "XY", "PYXQR")]:
    calls = [0]
    print(f"{c!r} from {a!r} and {b!r}: {interleaves(a, b, c, calls=calls)}, {calls[0]} calls")
for n in (6, 8, 10):
    a = b = "A" * n
    c = "A" * (2 * n - 1) + "B"  # all letters equal except the last: every split is tried before the answer, False
    calls = [0]
    print(f"{2 * n} letters, every one but the last equal: {interleaves(a, b, c, calls=calls)}, {calls[0]:,} calls")
for log, code in [("ERRORERROR", "ERR"), ("OKERRKOERR", "OK")]:
    print(f"{code!r} in {log!r}: {count_ways(log, code)}")
print(f"a code of 3 letters in a log of 10,000: {comb(10_000, 3):,} position sets")

'PXQYR' from 'PQR' and 'XY': True, 6 calls
'PYXQR' from 'PQR' and 'XY': False, 2 calls
12 letters, every one but the last equal: False, 2,507 calls
16 letters, every one but the last equal: False, 35,749 calls
20 letters, every one but the last equal: False, 520,675 calls
'ERR' in 'ERRORERROR': (18, 120)
'OK' in 'OKERRKOERR': (2, 45)
a code of 3 letters in a log of 10,000: 166,616,670,000 position sets

What to notice

• The broadcast position is not a third index. After i letters of a and j of b, the next letter of c is at position i + j, so the pair (i, j) says everything: about a million pairs at the limits.
• A count makes two choices per log letter: skip it, or use it for the next code letter when they are equal. The state is how much of the log has been read and how much of the code is spelled.

The interleaving table marks the pairs (i, j) that a valid merge can reach, and one row of it is enough. Taking a letter from the first queue whenever it fits is a greedy shortcut that fails. The counting table adds up the two choices, and one row filled from right to left uses each log letter once. Counts past 64 bits need a modulus or big integers.

The interleaving table Pro: opens with a Pro, Premium or Ultimate pass