Longest Common Subsequence

MediumDynamic Programming (1-D & 2-D)Blind 75MidOpen on LeetCodeUpdated Sep 21, 2026

You're given two strings text1 and text2. Return the length of their longest common subsequence, or 0 if they have none. A subsequence is what remains after deleting zero or more characters without reordering the rest, so "ace" is a subsequence of "abcde" but "aec" is not. A common subsequence is a subsequence of both strings, and its characters don't need to be next to each other in either one.

Examples

text1 = "abcde", text2 = "ace" returns 3

Rows are text1, columns are text2. Each kept match sits below and to the right of the one before.

"ace" appears in order in both strings; text1 just skips "b" and "d". Nothing longer is possible because text2 has only 3 characters.

text1 = "abc", text2 = "cba" returns 1

Every letter matches, but each match sits down and to the left of the one before, so no two can be kept together.

The strings share all three letters, but in opposite order. Keeping two of them, like "a" then "b", fails because "a" comes after "b" in text2, so only one letter survives.

text1 = "abc", text2 = "def" returns 0

No character appears in both strings.

Constraints

1 <= text1.length, text2.length <= 1000
text1 and text2 consist of only lowercase English characters.

Hints

Hint 1

Compare the last characters of the two strings. If they're equal, what's left to solve? If they differ, which character could you drop?

Hint 2

A pointer toward the approach

Hint 3

The full approach, step by step

Drill This: Your Approach First

Answer, Then Reveal

In two or three sentences, how would you solve it and what's the complexity?

Skip to Reading

Approach

Let dp[i][j] be the length of the longest common subsequence of the first i characters of text1 and the first j of text2, with row 0 and column 0 equal to 0. If text1[i-1] == text2[j-1], that pair can end the subsequence, so dp[i][j] = dp[i-1][j-1] + 1; otherwise one of the two last characters goes unused, so dp[i][j] = max(dp[i-1][j], dp[i][j-1]). Return dp[m][n]. O(m * n) time and space for lengths m and n; keeping two rows cuts space to O(min(m, n)).

Time

O(m * n)

Space

O(m * n)

Pitfall

On a match, writing max(dp[i-1][j], dp[i][j-1]) + 1 instead of dp[i-1][j-1] + 1. That lets one character pair up twice, so "a" vs "aa" wrongly scores 2.

Solutions

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length(), n = text2.length();
        int[][] dp = new int[m + 1][n + 1]; // dp[i][j]: answer for text1[0..i), text2[0..j)
        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];
    }
}

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