78. Longest Common Subsequence

MediumDynamic Programming (2-D)Also on LeetCode ↗

Return the length of the longest subsequence present in both strings (characters in order, not necessarily adjacent). Return 0 if there is none.

Example 1

Input: text1 = "abcde", text2 = "ace"

Output: 3

Explanation: The LCS is “ace”.

Example 2

Input: text1 = "AGGTAB", text2 = "GXTXAYB"

Output: 4

Explanation: The LCS is “GTAB”.

Hint 1

Compare the last characters of the two prefixes.

Hint 2

If they match, the LCS grows by one; otherwise drop one character from either string.

Dynamic ProgrammingString

Reference solution for 2-D DP table (time O(m · n), space O(m · n), or O(n) with one row). Each solution passes every test in all four languages.

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m, n = len(text1), len(text2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]     # dp[i][j]: LCS of text1[:i], text2[:j]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if text1[i - 1] == text2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1      # match: extend the diagonal
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        return dp[m][n]

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

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m = text1.size(), n = text2.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++)
                dp[i][j] = text1[i - 1] == text2[j - 1] ? dp[i - 1][j - 1] + 1 : max(dp[i - 1][j], dp[i][j - 1]);
        return dp[m][n];
    }
};

function longestCommonSubsequence(text1, text2) {
  const m = text1.length, n = text2.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++)
      dp[i][j] = text1[i - 1] === text2[j - 1] ? dp[i - 1][j - 1] + 1 : Math.max(dp[i - 1][j], dp[i][j - 1]);
  return dp[m][n];
}

Try solving it yourself first. Interviewers care more about how you explain the approach than about the finished code.

Language

78. Longest Common Subsequence

Example 1

Example 2

Approach 1: Recursion

Approach 2: 2-D DP table ✅