A subsequence keeps characters in order but may skip some: "ace" is a subsequence of "abcde". The longest common subsequence (LCS) of two strings measures how similar they are; tools that show the differences between two files use it.

Subproblem: table[i][j] is the LCS length of the first i characters of a and the first j of b. If those last characters match, they extend the LCS of both strings without them; otherwise, drop the last character of one string or the other, whichever is better:

def lcs(a, b):
    table = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
    for i in range(1, len(a) + 1):
        for j in range(1, len(b) + 1):
            if a[i - 1] == b[j - 1]:
                table[i][j] = table[i - 1][j - 1] + 1
            else:
                table[i][j] = max(table[i - 1][j], table[i][j - 1])
    return table[len(a)][len(b)]

print(lcs("abcde", "ace"))
print(lcs("PYTHON", "TYPHOON"))