Longest Common Subsequence (LCS)
What common mistakes do candidates make around Longest Common Subsequence (LCS), and how do you avoid them?
Answers use simple, clear English.
Quick interview answer
Common mistakes: Confusing subsequence with substring (contiguous); off-by-one on empty base row/col. Best practices: Fill dp table with 0-indexed strings + sentinel row/col; trace back for reconstruction.
Detailed answer
Common mistakes: Confusing subsequence with substring (contiguous); off-by-one on empty base row/col. Best practices: Fill dp table with 0-indexed strings + sentinel row/col; trace back for reconstruction. Core: Classic 2D DP: if s[i]==t[j], dp[i][j]=dp[i-1][j-1]+1 else max(dp[i-1][j], dp[i][j-1]). Subsequence allows gaps; not substring. Real-time example: Git diff: LCS of two file lines gives minimal edit script baseline for diff algorithms. Pros: Foundation for edit distance, diff tools, bioinformatics alignment. Cons: O(mn) time and space; Hirschberg or rolling array for space optimization. Common mistakes: Confusing subsequence with substring (contiguous); off-by-one on empty base row/col. Best practices: Fill dp table with 0-indexed strings + sentinel row/col; trace back for reconstruction. Audience level: Fresher.
Full explanation
Classic 2D DP: if s[i]==t[j], dp[i][j]=dp[i-1][j-1]+1 else max(dp[i-1][j], dp[i][j-1]). Subsequence allows gaps; not substring.
Real example & use case
Git diff: LCS of two file lines gives minimal edit script baseline for diff algorithms.
Pros & cons
Pros: Foundation for edit distance, diff tools, bioinformatics alignment. Cons: O(mn) time and space; Hirschberg or rolling array for space optimization.
Common mistakes
Confusing subsequence with substring (contiguous); off-by-one on empty base row/col.
Best practices
Fill dp table with 0-indexed strings + sentinel row/col; trace back for reconstruction.
Follow-up questions
- How would you test Longest Common Subsequence (LCS)?
- What metrics prove Longest Common Subsequence (LCS) is healthy in prod?
- How does Longest Common Subsequence (LCS) change at 10× traffic?