💬 Discord
Sign In
NeetCode #716LC-1143Medium2-D Dynamic ProgrammingBlind 75NC 150NC 250
← Back to All Problems

#716 · #1143 · Longest Common Subsequence(最长公共子序列)

📌 Problem Statement & Constraints

Given strings text1 and text2, return the length of their longest common subsequence, or 0 if none exists. A subsequence preserves relative order but need not be contiguous. Constraints: 1 <= text1.length, text2.length <= 1000, lowercase English letters.

💡 Core Algorithmic Approaches

  1. dp[i][j] is the LCS length of text1[0..i-1] and text2[0..j-1].
  2. If the last characters match, they extend the LCS of the shorter prefixes: dp[i][j] = dp[i-1][j-1] + 1.
  3. Otherwise drop one of the two last characters: dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
  4. The extra row and column of zeros encode the empty prefix and handle the base cases.

💻 Benchmark Python3 Implementation

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 Deep Dive

⏱️ Time Complexity
O(m * n): each pair of prefixes is solved once.
💾 Space Complexity
O(m * n), reducible to O(min(m, n)) with two rows.

⚠️ Interview Pitfalls & Follow-ups

  • Indexing the strings at i/j instead of i-1/j-1: the DP is offset by one to make room for the empty prefix.
  • Adding 1 when the characters differ: the +1 applies only on a match.
  • Confusing subsequence with substring: a substring must be contiguous and needs a different DP.
  • Omitting the all-zero first row and column: they are the base cases for the empty string.