01
Longest common subsequence (DP — Strings Sub-pattern)
The longest common subsequence table and the questions built on it: deletions to make two strings equal, the shortest common supersequence, repeating subsequences, counting how many times t appears in s.
Signals in the problem statement
- ›
"longest common subsequence"
- ›
"minimum deletions to make the strings equal"
- ›
"shortest string that has both as subsequences"
- ›
"number of distinct subsequences"
What makes it different
The table is always LCS-shaped. Some answers are read from it (n + m − 2·LCS), some walk back through it to build a string, and counting uses + instead of max.
Questions
ordered from “learn the idea” to “recognise it without help”- 1Longest Common SubsequenceWalkthroughMediumBasic Anchor·LeetCode #1143
- 2Delete Operation for Two StringsWalkthroughMediumBasic Reinforcement·LeetCode #583
- 3Longest Repeating SubsequenceWalkthroughMediumSlight Variation·GeeksforGeeks
- 4Shortest Common SupersequenceWalkthroughHardInterview-Level·LeetCode #1092
- 5Distinct SubsequencesWalkthroughHardTricky / Edge Case·LeetCode #115
Template
lcs-template.cpp
// LCS with two rows: dp[i][j] = LCS of the first i chars of a and the first j of b.
int lcs(const string& a, const string& b) {
int n = a.size(), m = b.size();
vector<int> prev(m + 1, 0), cur(m + 1, 0); // row 0 = empty prefix of a
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++)
cur[j] = a[i - 1] == b[j - 1] ? prev[j - 1] + 1 // both last chars used
: max(prev[j], cur[j - 1]); // drop one of them
swap(prev, cur);
}
return prev[m];
}Remember this · DP — Strings
Trigger
Longest common subsequence, edit distance, palindromes, matching with wildcards, interleaving.
Think
Look at the last characters: if they match, what do I do? If not, what are my options?
Key question
What does dp[i][j] mean, and what are the empty-string base cases?