Two hydrophones

Two recorders hang off one mooring at different depths and hear the same animal. Neither hears all of it; the survey needs the part they agree on.

The problem

Each hydrophone writes down the calls it can pick out of the noise, in arrival order, one letter per call: u upsweep, d downsweep, k knock, m moan. Neither log is complete — a call that comes through clearly at one depth can be lost at the other — but neither invents a call and neither reorders what it heard.

To line the logs up, the survey wants the longest sequence of calls appearing in both in the same order. Those calls need not be next to each other in either log; only their relative order has to match. Report its length.

Input. north and south — two non-empty strings of lowercase letters, the calls logged by each hydrophone in arrival order.

Output. The length of the longest call sequence that appears in both logs in order.

Example.

north = "udkmud", south = "dumdku"   ->  4

u, d, k, u appears in north at positions 0, 1, 2, 4 and in south at 1, 3, 4, 5. Nothing of length five is in both, and the longest stretch the logs share side by side is only two calls.

A second example, where one log is much shorter:

north = "umdku", south = "dkm"   ->  2

d then k. The m of north arrives before its d, so it cannot join them.

A third example, with nothing in common:

north = "uud", south = "kmk"   ->  0

Constraints.

• 1 <= len(north), len(south) <= 1000
• every character is a lowercase letter

Hints

Approach

Brute force

Generate every subsequence of one log and test each against the other: 2ⁿ candidates at O(m) each. Thirty calls is 10⁹ tests, and a log holds a thousand.

The insight

Every answer is decided by the last call of each prefix: when the two match they pair off, and when they differ, one of the two logs can spare its last call.

Write best[i][j] for the longest shared sequence using the first i calls of north and the first j of south. If those last calls are equal, pairing them loses nothing — any longer answer that skipped one can be rewritten to use both. If they differ, the two cannot both be used, so the answer is the better of the prefixes with one call dropped. Both branches point strictly backward, which is what lets the table be filled in one sweep.

Algorithm

1. Swap so north is the longer log, keeping the row short.
2. Hold a row prev of len(south) + 1 zeros — the answers against an empty prefix of north.
3. For each call of north, build cur: cur[j] = prev[j-1] + 1 when the calls are equal, otherwise the larger of prev[j] and cur[j-1].
4. Make cur the new prev; the last entry of the final row is the answer.

Complexity

Time O(n · m) — one entry per pair of prefixes, 10⁶ at the top of the range. Space O(min(n, m)) — two rows, because an entry reads only the row above and the cell to its left.

Solution

"""Two hydrophones — longest common subsequence, carried in two rows."""


def solve(north, south):
    if len(south) > len(north):
        north, south = south, north       # the narrow log becomes the row

    prev = [0] * (len(south) + 1)
    for call in north:
        cur = [0] * (len(south) + 1)
        # cur[j] = the best shared sequence from this much of north and j of south
        for j, other in enumerate(south, 1):
            if call == other:
                cur[j] = prev[j - 1] + 1  # both logs spend this call together
            else:
                cur[j] = prev[j] if prev[j] >= cur[j - 1] else cur[j - 1]
        prev = cur
    return prev[len(south)]

TESTS = [
    (("udkmud", "dumdku"), 4),
    (("umdku", "dkm"), 2),
    (("uud", "kmk"), 0),
    (("u", "u"), 1),
    (("mmmm", "m"), 1),
    (("kmudkmud", "kmudkmud"), 8),
    (("dkmu", "umkd"), 1),
    (("u" * 300 + "d" * 300, "d" * 300 + "u" * 300), 300),
]

Pitfalls

• Solving for the longest shared run. Resetting to zero on a mismatch answers 2 on the first example instead of 4; adjacency is not required here.
• Updating one row in place. cur[j] needs prev[j-1], the value from before this call was processed; a single array walked left to right has overwritten it.
• Tallying call types. Counting how many of each letter both logs hold ignores order: "dkmu" and "umkd" share all four types and agree on one call.

Variants

• Blends off the blotter — subsequences of one sequence, counted rather than measured against a second.
• Two sequences — the lesson this table comes from.