69. Longest Common Subsequence

MediumString Dynamic Programming

Given two strings text1 and text2, return the length of their longest common subsequence, or 0 if they share no characters.

A subsequence is what remains after deleting any number of characters (possibly none) without changing the order of the rest. For example, "one" is a subsequence of "stone". A common subsequence is one that is a subsequence of both strings.

Example 1

Input: text1 = "stone", text2 = "longest"
Output: 3

Explanation: "one" appears in order in both strings, and no common subsequence of length 4 exists.

Example 2

Input: text1 = "abc", text2 = "abc"
Output: 3

Example 3

Input: text1 = "abc", text2 = "def"
Output: 0

Constraints

1 <= text1.length, text2.length <= 1000
Both strings consist of lowercase English letters

Follow-up: Reconstruct one longest common subsequence itself, not just its length.

💡 Hint 1

Compare the last characters. If they are equal, they can end the common subsequence. If not, one of them is not part of it.

💡 Hint 2

Let dp[i][j] be the answer for the first i characters of text1 and the first j of text2. Then dp[i][j] = dp[i-1][j-1] + 1 on a match, else max(dp[i-1][j], dp[i][j-1]).

💡 Hint 3

Each row only depends on the previous one, so two rows of length n + 1 are enough.

Try it yourself first ✎

Solutions stick better after a real attempt. Peek when you're ready.

Approach

Classic 2D DP on prefixes. dp[i][j] is the LCS length of text1[0..i) and text2[0..j), with row and column 0 equal to 0. If text1[i-1] === text2[j-1], that character extends the best answer for the two shorter prefixes: dp[i-1][j-1] + 1. Otherwise drop the last character of one string or the other and take max(dp[i-1][j], dp[i][j-1]). Since row i only reads row i - 1, keep two rows and swap them.

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

function longestCommonSubsequence(text1, text2) {
  const n = text2.length;
  let prev = new Array(n + 1).fill(0);
  let curr = new Array(n + 1).fill(0);
  for (let i = 1; i <= text1.length; i++) {
    for (let j = 1; j <= n; j++) {
      curr[j] = text1[i - 1] === text2[j - 1] ? prev[j - 1] + 1 : Math.max(prev[j], curr[j - 1]);
    }
    [prev, curr] = [curr, prev];
  }
  return prev[n];
}

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

/**
 * @param {string} text1
 * @param {string} text2
 * @return {number}
 */
function longestCommonSubsequence(text1, text2) {

}

Ctrl/⌘ + ' run · Ctrl/⌘ + Enter submit