DP — Strings Pattern: Algorithmic Intuition, Sub-patterns & C++ Guide
Compare two strings (or one string with itself) with a table where dp[i][j] describes the first i and j characters.
4 sub-patterns · 17 questions
What is this pattern?
String DP compares prefixes. For two strings a and b, dp[i][j] describes the first i characters of a and the first j characters of b. Row 0 and column 0 are the empty prefix, and they are the base cases.
Every cell looks at the last characters a[i − 1] and b[j − 1]:
- They match → use the diagonal
dp[i − 1][j − 1](and add 1 for LCS). - They don't → one of them is not used, or must be changed: take the best of
dp[i − 1][j](dropa's last),dp[i][j − 1](dropb's last) and, for edit distance,dp[i − 1][j − 1](replace).
Fill row by row; each cell reads only its top, left and top-left neighbours, so two rows (or one row plus a saved diagonal) are enough.
Two relatives use the same table with a twist:
- Common substring: a mismatch resets the run to 0, and the answer is the biggest cell anywhere.
- Palindromes: one string with itself,
dp[i][j]abouts[i..j], filled by increasing length (or by expanding around each centre).
Two people reading their strings from the end, one letter at a time. If the last letters agree, they both move on together and score a point. If not, one of them skips a letter — and they try both ways, keeping the better result. The table remembers every "you're at letter i, I'm at letter j" situation so nobody re-reads.
See it move
Purple = the cells the rule reads. Green = a match. Gold = the walk back that rebuilds the subsequence.
a = "abcde", b = "ace"step 1/21dp[i][j] = the LCS of the first i letters of a and the first j letters of b. With an empty prefix (∅) there is nothing in common, so row 0 and column 0 are 0.
Top = delete a's letter, left = insert b's letter, diagonal = replace (free on a match). Purple = the cells read.
a = "horse", b = "ros"step 1/16Turning "" into j letters takes j inserts (row ∅); turning i letters into "" takes i deletes (column ∅).
How do I recognise it?
Two strings (or arrays) and "longest common subsequence / substring".
"Minimum operations to turn A into B" — insert, delete, replace (edit distance), or deletions with a cost.
Matching a string against a pattern with
?,*or.— the answer is true / false."Can s3 be formed by interleaving s1 and s2".
"Palindromic substrings / subsequence", "fewest insertions / cuts to make palindromes".
"Number of distinct subsequences of s equal to t".
Looks like DP — Strings, but isn't
A greedy walk with one pointer per string is enough — matching the first possible character is always safe. DP is for longest / count / cost.
An exact pattern needs no choices, so no table of prefixes.
One string and a validity rule on a window; nothing is compared prefix-to-prefix.
Order doesn't matter there, and DP is all about order.
How would I discover it from scratch?
Don't memorise “use dp — strings”. Ask these questions in order — the pattern falls out.
Recurse on the last characters: lcs(i, j) = match ? 1 + lcs(i − 1, j − 1) : max(lcs(i − 1, j), lcs(i, j − 1)). Each mismatch branches in two → about O(2^(N+M)).
Sub-patterns
Same core idea, different rule for “valid”. Learn them in this order.
Longest common subsequence
5 questionsThe 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.
Edit distance / matching
5 questionsEach cell picks the cheapest operation (insert / delete / replace), or for patterns decides true / false with the rule for ?, * or ..
Common substring
2 questionsLike LCS, but the common part must be contiguous: dp[i][j] is the length of the common run ending exactly at a[i − 1] and b[j − 1].
Palindrome DP
5 questionsOne string. dp[i][j] is about s[i..j], built from the shorter piece s[i+1..j−1], or computed by expanding from every centre.
Don't mix these up
Gaps allowed → mismatch takes max(top, left), answer in the corner. No gaps → mismatch is 0, answer is the max cell.
Without replace (only insert / delete) they are equal. With replace, one replace does the job of a delete plus an insert, so edit distance can be smaller.
Wildcard * matches any sequence by itself. Regex x* means zero or more copies of x — the star belongs to the character before it.
Subsequence = LCS(s, reverse s) works. Substring: a common substring of s and its reverse need not be a palindrome — use centres or the s[i..j] table.
Code templates (C++)
LCS (two rows)
Match → diagonal + 1, otherwise max(top, left). Variants change the base row and the combine: deletions, supersequence, counts (+).
// 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];
}Edit distance
Save the old diagonal before overwriting. Base row/column are j and i. Wildcard / regex matching use the same loop with booleans.
// Edit distance in one row: fewest insert / delete / replace to turn a into b.
int editDistance(const string& a, const string& b) {
int n = a.size(), m = b.size();
vector<int> dp(m + 1);
for (int j = 0; j <= m; j++) dp[j] = j; // "" -> b[0..j): j inserts
for (int i = 1; i <= n; i++) {
int diag = dp[0]; // dp[i - 1][0]
dp[0] = i; // a[0..i) -> "": i deletes
for (int j = 1; j <= m; j++) {
int top = dp[j]; // dp[i - 1][j]
if (a[i - 1] == b[j - 1]) dp[j] = diag; // last chars match: free
else dp[j] = 1 + min({top, // delete a[i - 1]
dp[j - 1], // insert b[j - 1]
diag}); // replace
diag = top;
}
}
return dp[m];
}Longest common substring
A mismatch resets to 0 and the answer is the best cell anywhere. One row works if j goes high → low.
// Longest common substring: dp[j] = length of the common run ending at a[i - 1] and b[j - 1].
// A mismatch breaks the run (0). j goes high -> low so dp[j - 1] is still the previous row.
int longestCommonSubstring(const string& a, const string& b) {
int m = b.size(), best = 0;
vector<int> dp(m + 1, 0);
for (size_t i = 1; i <= a.size(); i++)
for (int j = m; j >= 1; j--) {
dp[j] = a[i - 1] == b[j - 1] ? dp[j - 1] + 1 : 0;
best = max(best, dp[j]); // the answer can end anywhere
}
return best;
}Palindromes by expanding centres
2N − 1 centres (each character, and each gap). Count every expansion for "how many", keep the widest for "longest".
// Expand around each of the 2N - 1 centres (a character, or the gap between two).
// Every successful expansion is one more palindromic substring.
int countPalindromes(const string& s, int& bestStart, int& bestLen) {
int n = s.size(), count = 0;
bestStart = 0; bestLen = n ? 1 : 0;
for (int centre = 0; centre < 2 * n - 1; centre++) {
int l = centre / 2, r = l + centre % 2; // odd: l == r, even: r = l + 1
while (l >= 0 && r < n && s[l] == s[r]) {
count++;
if (r - l + 1 > bestLen) { bestLen = r - l + 1; bestStart = l; }
l--; r++;
}
}
return count; // longest = s.substr(bestStart, bestLen)
}