Longest Common Subsequence

Problem Description

Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

• For example, "ace" is a subsequence of "abcde".

A common subsequence of two strings is a subsequence that is common to both strings.

Examples

Constraints

• 1 ≤ text1.length, text2.length ≤ 1000
• text1 and text2 consist of only lowercase English characters.

Matching Characters and Slicing Subproblems

To find the longest common subsequence of two strings text1 and text2, we compare their characters starting from the end (or beginning).

For any two suffix positions i and j:

• If text1[i] == text2[j], the current characters match. This character is part of our subsequence. We add 1 to our count and recursively solve the remainder: 1 + lcs(i + 1, j + 1).
• If text1[i] != text2[j], the characters do not match. We have two choices: we can either ignore text1[i] and search the rest of text1 against text2, or ignore text2[j] and search text1 against the rest of text2. We take the maximum of these branches: max(lcs(i + 1, j), lcs(i, j + 1)).

This recursive structure allows 2D tabulation bottom-up. By creating a grid of size (m + 1) × (n + 1) and filling it from bottom-right to top-left, dp[0][0] will contain the maximum LCS length.

Solution 1: 2D Dynamic Programming (Grid Tabulation)

Create a 2D grid where dp[i][j] represents the LCS length of substrings starting at index i and j.

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];

        // build grid from bottom-right to top-left
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                if (text1.charAt(i) == text2.charAt(j)) {
                    dp[i][j] = 1 + dp[i + 1][j + 1]; // matching characters
                } else {
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j + 1]); // mismatch: try both paths
                }
            }
        }
        return dp[0][0];
    }
}

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)]

        # build grid from bottom-right to top-left
        for i in range(m - 1, -1, -1):
            for j in range(n - 1, -1, -1):
                if text1[i] == text2[j]:
                    dp[i][j] = 1 + dp[i + 1][j + 1]  # matching characters
                else:
                    dp[i][j] = max(
                        dp[i + 1][j], dp[i][j + 1]
                    )  # mismatch: try both paths

        return dp[0][0]

#include <string>
#include <vector>
#include <algorithm>

class Solution {
public:
    int longestCommonSubsequence(std::string text1, std::string text2) {
        int m = text1.length();
        int n = text2.length();
        std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1, 0));

        // build grid from bottom-right to top-left
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                if (text1[i] == text2[j]) {
                    dp[i][j] = 1 + dp[i + 1][j + 1]; // matching characters
                } else {
                    dp[i][j] = std::max(dp[i + 1][j], dp[i][j + 1]); // mismatch: try both paths
                }
            }
        }
        return dp[0][0];
    }
};

Complexity Analysis:

• Time Complexity: O(m * n) where m and n are the lengths of text1 and text2. We evaluate every grid cell once.
• Space Complexity: O(m * n) to store the 2D grid.

Where it breaks: On long strings (length 1000 each), allocating a 1000x1000 integer matrix requires 4MB of memory. This is fine, but can be optimized to O(n) space by keeping only the current and previous rows in memory, which is a common interview follow-up.

Common Mistakes

• Incorrect grid dimension allocation. The grid must be sized (m + 1) × (n + 1), not m × n, to accommodate the base cases of empty subproblem comparisons (indices at m and n which default to 0).
• Evaluating out-of-bounds indices inside loops. By starting the loops from m - 1 and n - 1 and accessing i + 1 and j + 1, we stay within bounds of the allocated (m + 1) × (n + 1) grid.
• Using non-contiguous character checks. Subsequence elements must preserve relative ordering but do not need to be contiguous. Do not confuse this with “Longest Common Substring”.

Frequently Asked Questions

How can we optimize the space complexity of this solution? Since the update for dp[i][j] only requires values from the current row i and the row below i + 1, we can store only two rows of size n + 1 (or even a single row by tracking a temporary diagonal variable), reducing space complexity to O(min(m, n)).

What is the difference between subsequence and substring? A substring is a contiguous slice of a string (e.g. "bcd" inside "abcde"). A subsequence is a sequence of characters that appear in the same relative order but can have gaps (e.g. "ace" inside "abcde").

What does this problem test in interviews? It tests your ability to model two-dimensional dynamic programming relationships and write bottom-up nested loops with offset index boundaries.

← All Problems