Longest Common Subsequence

Medium Problem 129 of 151 Java and Python

Problem

Given two strings text1 and text2, return the length of their longest common subsequence, or 0 if there is none.

A subsequence keeps the original order of characters but may delete some (for example "ace" is a subsequence of "abcde").

Example 1

Input: text1 = "abcde", text2 = "ace"
Output: 3
Why: "ace".

Example 2

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

Constraints

1 ≤ text1.length, text2.length ≤ 1000

Explanation

Compare the strings from their ends. If the last characters match, they are part of the LCS: 1 + LCS(both without their last char). If not, drop the last character of one string or the other and take the better result.

dp[i][j] = LCS of the first i characters of text1 and the first j of text2 fills an (m + 1) × (n + 1) table.

Approach 1 · Naive

Plain recursion

Time O(2^(m + n))
Space O(m + n)

Apply the match / skip rule recursively from the ends.

lcs(i, j): 0 if either is 0.
If text1[i-1] == text2[j-1], return 1 + lcs(i-1, j-1); else max(lcs(i-1, j), lcs(i, j-1)).

Java

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        return lcs(text1, text2, text1.length(), text2.length());
    }

    private int lcs(String a, String b, int i, int j) {
        if (i == 0 || j == 0) {
            return 0;
        }
        if (a.charAt(i - 1) == b.charAt(j - 1)) {
            return 1 + lcs(a, b, i - 1, j - 1);
        }
        return Math.max(lcs(a, b, i - 1, j), lcs(a, b, i, j - 1));
    }
}

Python

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        def lcs(i, j):
            if i == 0 or j == 0:
                return 0
            if text1[i - 1] == text2[j - 1]:
                return 1 + lcs(i - 1, j - 1)
            return max(lcs(i - 1, j), lcs(i, j - 1))

        return lcs(len(text1), len(text2))

Approach 2 · Optimal

Bottom-up DP table

Time O(m · n)
Space O(m · n) (O(n) with two rows)

Fill dp[i][j] row by row using the same rule; row 0 and column 0 are zeros.

Create dp of size (m + 1) × (n + 1) filled with 0.
For each i, j: if the characters match, dp[i][j] = dp[i-1][j-1] + 1; else max(dp[i-1][j], dp[i][j-1]).
Return dp[m][n].

Java

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length();
        int 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++) {
                if (text1.charAt(i - 1) == text2.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];
    }
}

Python

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

Complexity compared

Approach	Time	Space
Naive Plain recursion	O(2^(m + n))	O(m + n)
Optimal Bottom-up DP table	O(m · n)	O(m · n) (O(n) with two rows)

Key takeaways

Most "two strings" DP problems (Edit Distance, Distinct Subsequences, Interleaving String) use this exact table.
Padding with an extra row and column of zeros removes boundary checks.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem