Longest Common Subsequence

MediumString Dynamic Programming

Diff tools line up two versions of a text by finding what they have in common: the longest sequence of characters that appears in both versions in the same order, though not necessarily side by side. Everything outside that shared sequence is then shown as an insertion or a deletion.

Given two strings text1 and text2, return the length of their longest common subsequence, or 0 if they share no character. A subsequence keeps the order of the characters it uses but may skip any others: "rot" is a subsequence of "robot", while "tor" is not.

Example 1

Input: text1 = "draft", text2 = "drift"
Output: 4

Explanation: "drft" appears in order in both versions; only the vowel differs.

Example 2

Input: text1 = "release", text2 = "relapse"
Output: 6

Explanation: "relase" fits into both words in order, so six characters line up.

Example 3

Input: text1 = "moon", text2 = "fire"
Output: 0

Explanation: The two strings have no letter in common.

Constraints

text1 and text2 are each between 1 and 1000 characters long.
Both strings use only 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