Domain 2MediumMEDIUM

Longest Common Subsequence

Calculate the length of the longest common subsequence between two strings using a 2D dynamic programming table.

Domain: medium•Updated: 2026-09-09
#Dynamic Programming#2D Array#$O(N^2)$ Time Complexity#$O(M times N)$ Space Complexity

Problem Breakdown

We are asked to find the length of the longest string that appears as a subsequence in both input strings (text1 and text2). A key distinction here is “subsequence” versus “substring”: characters must maintain their relative order but do not need to be contiguous.

Inputs: Two strings, text1 and text2. Output: An integer representing the maximum length of a common subsequence (0 if none exists).

Constraints & Edge Cases:

  • Lengths are between 1 and 1000. This suggests an O(N2)O(N^2) solution is acceptable (10610^6 operations), but we must be mindful of memory usage for the DP table.
  • Characters are lowercase English letters only (no special handling needed for unicode or symbols).
  • While constraints say lengths ≥1\ge 1, a robust algorithm should logically handle empty strings by returning 0, which our initialization naturally supports.

Intuition

If we try to solve this recursively without optimization, we would explore every possible combination of characters from text1 and check if they exist in text2. This leads to an exponential time complexity O(2N)O(2^N) because the same subproblems (calculating LCS for specific prefixes) get recalculated repeatedly.

The core insight is that this problem exhibits optimal substructure and overlapping subproblems. The decision at any point depends on whether characters match or not:

  1. If text1[i] == text2[j], we can extend the LCS found so far by adding one character to it.
  2. If they don’t match, we must skip either text1[i] or text2[j]. The result is the maximum of these two choices.

This structure maps perfectly onto a Dynamic Programming (DP) table where each cell represents the LCS length for specific prefixes of both strings.

Approach

We will construct a 2D DP matrix, dp, with dimensions (len(text1) + 1) by (len(text2) + 1). The extra row and column represent empty prefix cases (base case), which always have an LCS length of 0.

Algorithm Steps:

  1. Initialize the DP table filled with zeros.
  2. Iterate through each character index i for text1 and j for text2.
  3. Match Case: If characters match (text1[i] == text2[j]), then dp[i+1][j+1] = dp[i][j] + 1. We take the diagonal value (representing LCS of previous prefixes) and increment it because we found a common character to extend that subsequence.
  4. Mismatch Case: If characters do not match, we cannot form an extension using this specific pair. The best result is max(dp[i][j+1], dp[i+1][j]). This means either skipping the current char in text2 or skipping the current char in text1, whichever yields a longer subsequence found previously.
  5. After filling the table, return the value at dp[len(text1)][len(text2)].

Complexity Analysis

  • Time Complexity: O(m×n)O(m \times n), where mm and nn are lengths of text1 and text2. We visit every cell in the DP matrix exactly once. Given constraints up to 1000 characters, this is roughly 10610^6 operations, which fits well within typical time limits (usually ~1 second for ≈108\approx 10^8 ops).
  • Space Complexity: O(m×n)O(m \times n) for the DP table. With lengths of 1000, we allocate approximately 4MB of memory (assuming integers), which is negligible compared to standard heap limits.

Solution

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m = len(text1)
        n = len(text2)
        
        # Initialize DP table with (m+1) rows and (n+1) columns.
        # dp[i][j] stores the LCS length for text1[:i] and text2[:j].
        dp = [[0] * (n + 1) for _ in range(m + 1)]

        # Iterate through both strings using indices i and j.
        # We use ranges up to m/n because we access dp[i+1][j+1], 
        # effectively processing the character at text1[i].
        for i, char1 in enumerate(text1):
            for j, char2 in enumerate(text2):
                if char1 == char2:
                    # Characters match. Extend the LCS from previous diagonal state + 1.
                    dp[i+1][j+1] = dp[i][j] + 1
                else:
                    # Characters mismatch. Take max of skipping current char in either string.
                    dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])

        return dp[m][n]