Longest Common Subsequence

medium dp string

Problem

Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0. A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

Inputa = "abcde", b = "ace"

Output3

"ace" is a common subsequence of length 3.

def longest_common_subsequence(a, b):
    m, n = len(a), len(b)
    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
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[m][n]

function longestCommonSubsequence(a, b) {
  const m = a.length, n = b.length;
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
  for (let i = 1; i <= m; i++) for (let j = 1; j <= n; j++) {
    if (a[i - 1] === b[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
    else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
  }
  return dp[m][n];
}

class Solution {
    public int longestCommonSubsequence(String a, String b) {
        int m = a.length(), n = b.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) for (int j = 1; j <= n; j++) {
            if (a.charAt(i - 1) == b.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1] + 1;
            else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
        }
        return dp[m][n];
    }
}

int longestCommonSubsequence(string a, string b) {
    int m = a.size(), n = b.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    for (int i = 1; i <= m; i++) for (int j = 1; j <= n; j++) {
        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[m][n];
}

Explanation

We want the longest string of characters that appears in both a and b in the same order (gaps allowed). This is a classic grid dynamic program that compares the two strings prefix by prefix.

We fill a table dp where dp[i][j] = the LCS length of the first i characters of a and the first j characters of b. The first row and column are 0, since an empty string shares nothing.

For each cell there are two cases. If the current characters match (a[i-1] == b[j-1]), we extend the diagonal answer: dp[i][j] = dp[i-1][j-1] + 1. If they don't match, we drop one character from either string and keep the better option: max(dp[i-1][j], dp[i][j-1]).

The bottom-right cell dp[m][n] holds the final answer.

Example: a = "abcde", b = "ace". The matches on a, c, and e stack up to give length 3.

Time: O(m·n) Space: O(m·n)