Intermediate LevelData Structures & Algorithms
How do you compute the Longest Common Subsequence (LCS)?
ā Interview Prompt: Explain LCS problem, 2D DP table construction, O(MN) time complexity, and difference from Longest Common Substring.
LCS vs LCS (Substring):
ā¢
Subsequence: Characters need not be contiguous (e.g., "ACE" is a subsequence of "ABCDE").
ā¢
Substring: Characters must be contiguous.
DP Recurrence:
Let dp[i][j] = LCS of s1[0..i-1] and s2[0..j-1].
```
if s1[i-1] === s2[j-1]: dp[i][j] = 1 + dp[i-1][j-1]
else: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
```
ā¢
Time: $O(M \times N)$, Space: $O(M \times N)$ (reducible to $O(\min(M,N))$).
Code Implementation Example
typescript
function longestCommonSubsequence(s1: string, s2: string): number {
const m = s1.length, n = s2.length;
const dp: number[][] = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (s1[i - 1] === s2[j - 1]) {
dp[i][j] = 1 + dp[i - 1][j - 1];
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[m][n];
}
console.log(longestCommonSubsequence("abcde", "ace")); // 3š”LCS 2D DP table ā O(MN) time and space.
šÆ Interview Key Takeaway
LCS is a foundational DP problem powering diff tools (git diff), spell checkers, and DNA sequence alignment. Master the 2D table and recurrence.
#DSA#LCS#Dynamic Programming#Subsequence#Intermediate
Back to all Data Structures & Algorithms Questionsā