How to Solve Longest Common Subsequence on LeetCode
The Longest Common Subsequence (LCS) problem is a foundational dynamic programming challenge on LeetCode, often asked in technical interviews for software engineering roles.
Problem Statement
Given two strings
text1andtext2, return the length of their longest common subsequence.
A subsequence is a sequence that appears in the same relative order, but not necessarily contiguous.
Example:
Input: text1 = "abcde", text2 = "ace"
Output: 3
Explanation: The LCS is "ace" (length 3).
Why This Problem Matters for Interviews
This problem:
- Tests your ability to recognize overlapping subproblems (DP)
- Demonstrates space/time optimization
- Is foundational for other string-matching questions
Dynamic Programming Approach to Longest Common Subsequence
1. Classic DP Table (Optimal)
Build a 2D DP table where dp[i][j] is the LCS length of text1[:i] and text2[:j].
Time Complexity: O(mn)
Space Complexity: O(mn)
def longestCommonSubsequence(text1: str, text2: str) -> int:
m, n = len(text1), len(text2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m):
for j in range(n):
if text1[i] == text2[j]:
dp[i+1][j+1] = dp[i][j] + 1
else:
dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])
return dp[m][n]
Key Interview Talking Points
- The definition and intuition behind subsequences.
- Why brute force recursion is exponential (2^n).
- How DP table avoids recomputation.
- How to recover the LCS string (not just length).
- Space optimization (use two rows).
Big O Complexity Recap
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| DP Table | O(mn) | O(mn) |
| Space-Optimized DP | O(mn) | O(min(m, n)) |
Pro Interview Tips
- Mention practical uses of LCS (diff tools, DNA sequencing).
- Always define “subsequence” in your explanation.
- Practice with test cases