They cannot form a matched pair. A valid optimum must skip at least one of those current characters, so compare advancing i with advancing j. Advancing both is already covered within those possibilities.

Let lcs(i,j) be the length of a longest common subsequence of suffixes a[i:] and b[j:].

from functools import cache

def common_length(a, b):
    @cache
    def lcs(i, j):
        if i == len(a) or j == len(b):
            return 0
        if a[i] == b[j]:
            return 1 + lcs(i + 1, j + 1)
        return max(lcs(i + 1, j), lcs(i, j + 1))
    return lcs(0, 0)

assert common_length("abc", "ac") == 2
assert common_length("abc", "xyz") == 0
assert common_length("", "abc") == 0

If the current characters match, there exists an optimum that pairs them: choosing these earliest equal positions leaves at least as much suffix available as pairing that first symbol later. After consuming that pair, solve the two smaller suffixes. This is a structural argument, not permission to greedily match arbitrary later letters.

The trace ("abc", "ac") matches a, then skips b, then matches c. State count is O(mn) with constant work each, giving O(mn) time and cache space, plus O(m+n) stack depth.

For edit distance, the same pair of bookmarks can support a different question: minimum edits to convert one suffix to the other. Transitions correspond to insertion, deletion, and replacement, with different costs and base cases. The state shape alone does not determine the recurrence.

Analogy limit: moving diagonally in this conceptual grid means consuming characters from both strings, not moving through a literal board.

No. A mismatch breaks a contiguous match. A useful different state measures the common suffix ending at a pair of positions; matches extend diagonally and mismatches reset that length to zero. Take the maximum over all endpoints.