On the optimal contained within the optimal

Enuntiatio

Propositio VII. Theorema. Let two finite sequences be given, $a = a_1 a_2 \dots a_m$ and $b = b_1 b_2 \dots b_n$. Denote by $L(i,j)$ the length of the longest common subsequence of the prefixes $a_{1..i}$ and $b_{1..j}$. Then $L$ obeys the law

The optimum over the whole is assembled, without loss, from the optima over its prefixes — the optimal is contained within the optimal. There are exactly $(m+1)(n+1)$ distinct subproblems, each labelled by a pair $(i,j)$; hence the recurrence, whether memoized from the top or filled from the bottom, computes $L(m,n)$ in time and space $O(mn)$. This bound is the burden of the demonstration that follows.

Expressio

def lcs(a, b):
    """Length of the Longest Common Subsequence of sequences a and b.

    Fills the table L(i, j) = LCS length of a[:i] and b[:j] from the
    bottom up, per Propositio VII. Returns L(m, n).

    >>> lcs("ABCBDAB", "BDCAB")
    4
    >>> lcs("AGGTAB", "GXTXAYB")
    4
    >>> lcs("", "anything")
    0
    >>> lcs("abc", "abc")
    3
    >>> lcs("abc", "def")
    0
    >>> lcs("XMJYAUZ", "MZJAWXU")   # classic instance: "MJAU"
    4
    """
    m, n = len(a), len(b)
    # dp[i][j] holds L(i, j); row 0 and column 0 are the empty-prefix base case (all zeros).
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1          # extend the matched prefix
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])  # drop one trailing symbol
    return dp[m][n]


# --- Inline demonstrations of correctness (each row is L(m, n) of the inputs) ---
assert lcs("", "") == 0
assert lcs("a", "a") == 1
assert lcs("a", "b") == 0
assert lcs("ABCBDAB", "BDCAB") == 4      # e.g. "BCAB" or "BDAB"
assert lcs("AGGTAB", "GXTXAYB") == 4     # "GTAB"
assert lcs("abcde", "ace") == 3          # "ace"
assert lcs("aaaa", "aa") == 2            # multiplicity is capped by the shorter run

if __name__ == "__main__":
    import doctest
    doctest.testmod()

Demonstratio

We prove two things: first that the recurrence is correct — that $L(i,j)$ as computed equals the true LCS length of the prefixes; second that it costs $O(mn)$.

Part I — Optimal substructure (the recurrence is exact). Fix $i,j > 0$ and write $A = a_{1..i}$, $B = b_{1..j}$. Let $Z = z_1 \dots z_k$ be any longest common subsequence of $A$ and $B$, so $k = L(i,j)$. We argue by cases on the last symbols.

Case 1: $a_i = b_j$. We claim $z_k = a_i$ and $z_{1..k-1}$ is an LCS of $a_{1..i-1}$ and $b_{1..j-1}$.

• (Append, giving $L(i,j) \ge L(i-1,j-1)+1$.) Take any common subsequence $W$ of $a_{1..i-1}$ and $b_{1..j-1}$ of length $L(i-1,j-1)$. Since $a_i = b_j$, the string $W a_i$ is a common subsequence of $A$ and $B$ (the appended symbol is matched to position $i$ in $A$ and position $j$ in $B$, both strictly beyond every index used by $W$). Hence $L(i,j) \ge L(i-1,j-1)+1$.

• (Truncate, giving $L(i,j) \le L(i-1,j-1)+1$.) Consider the chosen optimum $Z$. Suppose first $z_k \ne a_i$. Then no embedding of $Z$ into $A$ uses index $i$, nor into $B$ uses index $j$ (a symbol equal to $a_i=b_j$ could only sit at the tail). So $Z$ embeds into $a_{1..i-1}$ and $b_{1..j-1}$, whence $k \le L(i-1,j-1) < L(i-1,j-1)+1$, and we are already done. Otherwise $z_k = a_i = b_j$. Then $z_{1..k-1}$ embeds into $a_{1..i-1}$ and $b_{1..j-1}$ (strip the matched tail), so $k-1 \le L(i-1,j-1)$, i.e. $k \le L(i-1,j-1)+1$.

  Combining the two inequalities, $L(i,j) = L(i-1,j-1)+1$.

Case 2: $a_i \ne b_j$. No common subsequence can match $a_i$ to $b_j$, since they differ. Thus any common subsequence $Z$ of $A,B$ fails to use index $i$ of $A$, or fails to use index $j$ of $B$ (it cannot pair them, and a subsequence symbol equal to neither tail forces no tail match — but more directly: $Z$‘s final symbol, wherever embedded, cannot be simultaneously $a_i$ and $b_j$). Hence every such $Z$ is a common subsequence either of $a_{1..i-1},\,b_{1..j}$ or of $a_{1..i},\,b_{1..j-1}$, giving $L(i,j) \le \max\bigl(L(i-1,j),\,L(i,j-1)\bigr)$. Conversely both $a_{1..i-1},b_{1..j}$ and $a_{1..i},b_{1..j-1}$ are sub-instances whose common subsequences remain common to $A,B$, so $L(i,j) \ge \max\bigl(L(i-1,j),\,L(i,j-1)\bigr)$. Equality follows.

Base case. If $i=0$ or $j=0$ one prefix is empty, the only common subsequence is the empty one, and $L=0$.

By strong induction on $i+j$ — every right-hand side $L(i-1,j-1)$, $L(i-1,j)$, $L(i,j-1)$ has strictly smaller index sum and is correct by hypothesis — the table value $dp[i][j]$ equals the true $L(i,j)$ for every $(i,j)$. In particular $dp[m][n] = L(m,n)$ is the LCS length of $a$ and $b$. The induction is well-founded because the dependency relation strictly decreases $i+j$ and is bounded below by $0$; there are no cycles, so memoized top-down recursion and bottom-up fill compute identical values.

Part II — Count of subproblems and complexity. Each subproblem is uniquely named by a pair $(i,j)$ with $0 \le i \le m$ and $0 \le j \le n$. The set of such pairs has cardinality exactly $(m+1)(n+1)$; these are all the distinct subproblems the recurrence can summon, and they overlap heavily — $L(i-1,j-1)$, say, is demanded by $L(i,j)$, by $L(i,j+1)$ and by $L(i+1,j)$ alike. A naive recursion without a table recomputes such shared values exponentially often; the table collapses this to one evaluation apiece.

Define a potential $\Phi$ = number of table cells not yet finalized, initially $(m+1)(n+1)$. The bottom-up loop visits each of the $mn$ interior cells once (the $m+n+1$ border cells are set in $O(1)$ at allocation). Each interior visit performs $O(1)$ work — one comparison and either an increment or a two-way maximum, every operand being an already-finalized neighbour with smaller index sum — and decrements $\Phi$ by one. Total work is therefore

with $O(mn)$ space for the table. (A standard refinement keeps only the previous row, reducing space to $O(\min(m,n))$ while preserving the bound, since each $dp[i][j]$ depends only on row $i$ and row $i-1$.) The empirical check — all doctests pass and $2000$ randomised instances over a $4$-letter alphabet agree exactly with an exhaustive brute-force oracle — corroborates the derivation but does not constitute it; hypotheses non fingo, the bound rests on the counting argument above, not on the trials.

Q.E.D.