Problem statement

Given two strings, return the length of their longest common subsequence — the longest sequence of characters appearing in both strings in the same relative order (not necessarily contiguously). Return 0 if there is none.

Example 1

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

Example 2

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

Constraints

• 1 <= text1.length, text2.length <= 20
• Lowercase English letters.

Hints for Longest Common Subsequence

1. Hint 1

   dp[i][j]: LCS of the first i chars of text1 and first j of text2.

2. Hint 2

   Match → 1 + diagonal; otherwise max of dropping one character from either string.

How to solve Longest Common Subsequence

Compare the two strings position by position. If the current characters match, they can safely be paired up and the answer grows by one on top of both shorter prefixes. If they differ, at least one of the two characters is unused, so try dropping each and keep the better result.

Approach

1. Let dp[i][j] be the LCS length of the first i characters of text1 and the first j of text2.
2. Any prefix against an empty string gives 0 — that is the base row and column.
3. If text1[i-1] == text2[j-1], set dp[i][j] = dp[i-1][j-1] + 1.
4. Otherwise set dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
5. Return dp[len1][len2].

Why it works

When the characters match, there is always an optimal LCS that pairs them: if some optimal solution used them separately or not at all, it can be rewritten to pair them without getting shorter. When they differ they cannot both be the final matched pair, so at least one is droppable — and the two branches cover both possibilities. Prefixes give overlapping subproblems, which is why the table pays for itself: the same prefix pair would otherwise be recomputed exponentially often.

Complexity

• Time — O(len1 · len2)
• Space — O(len1 · len2)

Pitfalls

• Index the table by prefix length, so dp[i][j] uses text1[i-1] and text2[j-1] — the off-by-one here is the usual bug.
• Subsequences need not be contiguous; this is not the longest common substring, whose recurrence resets to 0 on a mismatch.
• The base row and column must both be zero-filled.
• The answer is at the bottom-right corner, not the table's maximum.

Reference solution

Python

def longestCommonSubsequence(text1: str, text2: str) -> int:
    n, m = len(text1), len(text2)
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, m + 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[n][m]

Java

public static int longestCommonSubsequence(String text1, String text2) {
    int n1 = text1.length(), n2 = text2.length();
    int[][] dp = new int[n1 + 1][n2 + 1];
    for (int i = 1; i <= n1; i++) {
        for (int j = 1; j <= n2; 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[n1][n2];
}

C++

int longestCommonSubsequence(string text1, string text2) {
    int n1 = (int) text1.size(), n2 = (int) text2.size();
    vector<vector<int>> dp(n1 + 1, vector<int>(n2 + 1, 0));
    for (int i = 1; i <= n1; i++) {
        for (int j = 1; j <= n2; j++) {
            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[n1][n2];
}

JavaScript

var longestCommonSubsequence = function(text1, text2) {
    const n = text1.length, m = text2.length;
    const dp = [];
    for (let i = 0; i <= n; i++) dp.push(new Array(m + 1).fill(0));
    for (let i = 1; i <= n; i++) {
        for (let j = 1; j <= m; 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[n][m];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Design a Food Rating System Medium
• Design Bitset Medium
• Iterator for Combination Medium
• Time Based Key-Value Store Medium
• Map Sum Pairs Medium
• Implement Magic Dictionary Medium