Longest common subsequence

Length of the longest sequence of characters that appears in both strings in the same order. The core of diff tools.

Time O(m × n)Space O(m × n)Code C++, Python and C#

Watch it animatedStep through it, with the running line highlighted. Free with an account.

The idea

dp[i, j] is the answer for the first i characters of a and the first j of b. If the two last characters match, extend the diagonal answer by one. Otherwise drop one character from either string and keep the better result.

Code

C++PythonC#

int lcs(const string& a, const string& b) {
    vector<vector<int>> dp(a.size() + 1, vector<int>(b.size() + 1, 0));
    for (int i = 1; i <= (int)a.size(); i++)
        for (int j = 1; j <= (int)b.size(); j++)
            dp[i][j] = a[i - 1] == b[j - 1]
                ? dp[i - 1][j - 1] + 1
                : max(dp[i - 1][j], dp[i][j - 1]);
    return dp[a.size()][b.size()];
}

def lcs(a: str, b: str) -> int:
    dp = [[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]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[len(a)][len(b)]

public static int Lcs(string a, string b) {
    var dp = new int[a.Length + 1, b.Length + 1];
    for (int i = 1; i <= a.Length; i++)
        for (int j = 1; j <= b.Length; j++)
            dp[i, j] = a[i - 1] == b[j - 1]
                ? dp[i - 1, j - 1] + 1
                : Math.Max(dp[i - 1, j], dp[i, j - 1]);
    return dp[a.Length, b.Length];
}

Tips

Row 0 and column 0 stay 0: an empty string has nothing in common with anything.
Walk back from the bottom-right corner along the choices to recover the subsequence itself.

In the .NET library

int[,] is a true rectangular 2D array: one allocation, indexed as dp[i, j]. It suits DP tables better than a jagged int[][].