DP on strings fills a table where dp[i][j] answers the question for prefixes s1[0..i-1] and s2[0..j-1].
Three classics share one skeleton:
Match → take diagonal + 1. Mismatch → combine neighbors.
Pattern 1: Longest Common Subsequence (LCS)
The LCS table filling for "ACE" vs "ABCDE" — matches add 1 to the diagonal, mismatches carry the best neighbor. Press ▶ to animate.
⚠️ Animation & Content Notice
The animation work is not fully finished — some animations may have slight errors.
If there is a major error in the content or if the animation or content is difficult to understand, please contact us at rayyancodingschool@gmail.com.
Longest Common Subsequence (Strings)
Length of the longest subsequence shared by two strings.
dp[i][j] over prefixes. If s1[i-1]==s2[j-1] take the diagonal +1; else inherit max(up, left). Matches trace diagonals, mismatches take the better neighbour. O(n·m) time and space.
1
for i in 1..m:
2
for j in 1..n:
3
if s1[i-1] == s2[j-1]:
4
dp[i][j] = dp[i-1][j-1] + 1
5
else: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
public int longestCommonSubsequence(String a, String b) {
int m = a.length(), n = b.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (a.charAt(i - 1) == b.charAt(j - 1))
dp[i][j] = dp[i - 1][j - 1] + 1;
else
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
return dp[m][n];
}def lcs(a, b):
m, n = len(a), len(b)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if a[i - 1] == b[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[m][n]int longestCommonSubsequence(string a, string b) {
int m = a.size(), n = b.size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
if (a[i - 1] == b[j - 1])
dp[i][j] = dp[i - 1][j - 1] + 1;
else
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
return dp[m][n];
}function lcs(a, b) {
const m = a.length,
n = b.length;
const dp = 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 (a[i - 1] === b[j - 1])
dp[i][j] = dp[i - 1][j - 1] + 1;
else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
return dp[m][n];
}
dp[i][j]speaks about prefixes — that’s why loops run1..mbut chars are[i-1].
Pattern 2: Edit Distance
Mismatch costs one operation — replace (diagonal), delete (up), insert (left):
public int minDistance(String a, String b) {
int m = a.length(), n = b.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 0; i <= m; i++) dp[i][0] = i; // delete all
for (int j = 0; j <= n; j++) dp[0][j] = j; // insert all
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
if (a.charAt(i - 1) == b.charAt(j - 1))
dp[i][j] = dp[i - 1][j - 1]; // free match
else
dp[i][j] = 1 + Math.min(
dp[i - 1][j - 1], // replace
Math.min(dp[i - 1][j], // delete
dp[i][j - 1])); // insert
return dp[m][n];
}def min_distance(a, b):
m, n = len(a), len(b)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1):
dp[i][0] = i # delete all
for j in range(n + 1):
dp[0][j] = j # insert all
for i in range(1, m + 1):
for j in range(1, n + 1):
if a[i - 1] == b[j - 1]:
dp[i][j] = dp[i - 1][j - 1] # free match
else:
dp[i][j] = 1 + min(
dp[i - 1][j - 1], # replace
dp[i - 1][j], # delete
dp[i][j - 1], # insert
)
return dp[m][n]int minDistance(string a, string b) {
int m = a.size(), n = b.size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1));
for (int i = 0; i <= m; i++) dp[i][0] = i; // delete all
for (int j = 0; j <= n; j++) dp[0][j] = j; // insert all
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
if (a[i - 1] == b[j - 1])
dp[i][j] = dp[i - 1][j - 1]; // free match
else
dp[i][j] = 1 + min({
dp[i - 1][j - 1], // replace
dp[i - 1][j], // delete
dp[i][j - 1] // insert
});
return dp[m][n];
}function minDistance(a, b) {
const m = a.length,
n = b.length;
const dp = Array.from({ length: m + 1 }, (_, i) =>
new Array(n + 1).fill(0).map((_, j) => (i === 0 ? j : i)),
);
// fix first column properly
for (let i = 0; i <= m; i++) dp[i][0] = i;
for (let i = 1; i <= m; i++)
for (let j = 1; j <= n; j++)
if (a[i - 1] === b[j - 1]) dp[i][j] = dp[i - 1][j - 1];
else
dp[i][j] =
1 +
Math.min(
dp[i - 1][j - 1], // replace
dp[i - 1][j], // delete
dp[i][j - 1], // insert
);
return dp[m][n];
}Base cases matter here: row 0 = “insert j chars”, column 0 = “delete i chars”.
Pattern 3: Longest Palindromic Subsequence
LPS(s) = LCS(s, reverse(s)). Or directly — fill by increasing window length:
public int longestPalindromeSubseq(String s) {
int n = s.length();
int[][] dp = new int[n][n];
for (int i = n - 1; i >= 0; i--) {
dp[i][i] = 1; // single char
for (int j = i + 1; j < n; j++) {
if (s.charAt(i) == s.charAt(j))
dp[i][j] = dp[i + 1][j - 1] + 2;
else
dp[i][j] = Math.max(dp[i + 1][j],
dp[i][j - 1]);
}
}
return dp[0][n - 1];
}def longest_palindromic_subseq(s):
n = len(s)
dp = [[0] * n for _ in range(n)]
for i in range(n - 1, -1, -1):
dp[i][i] = 1 # single char
for j in range(i + 1, n):
if s[i] == s[j]:
dp[i][j] = dp[i + 1][j - 1] + 2
else:
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
return dp[0][n - 1]int longestPalindromeSubseq(string s) {
int n = s.size();
vector<vector<int>> dp(n, vector<int>(n, 0));
for (int i = n - 1; i >= 0; i--) {
dp[i][i] = 1; // single char
for (int j = i + 1; j < n; j++)
if (s[i] == s[j])
dp[i][j] = dp[i + 1][j - 1] + 2;
else
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
}
return dp[0][n - 1];
}function longestPalindromicSubseq(s) {
const n = s.length;
const dp = Array.from({ length: n }, () => new Array(n).fill(0));
for (let i = n - 1; i >= 0; i--) {
dp[i][i] = 1; // single char
for (let j = i + 1; j < n; j++)
if (s[i] === s[j]) dp[i][j] = dp[i + 1][j - 1] + 2;
else dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
}
return dp[0][n - 1];
}Ends match → inner palindrome plus 2. Else drop either end and take the better.
Common Mistakes
Indexing s[i] when the loop runs 1..m.
dp[i][j] is about prefixes — the character is s[i-1].
Using max for edit distance mismatches.
Edit distance MINimizes over three options; LCS MAXimizes over two.
Iterating LPS row-major.
dp[i+1][j-1] must exist first — iterate i descending (or by gap).
Confusing subsequence with substring.
Subsequence skips characters; substring is contiguous. Different DPs entirely.
Complexity
| Problem | Time | Space |
|---|---|---|
| LCS | O(m·n) | O(m·n), reducible to O(min(m,n)) |
| Edit distance | O(m·n) | O(m·n) |
| LPS | O(n²) | O(n²) |
Premium Content
Unlock DP on Strings and all premium lessons with a subscription.
From ₹199.99/year — See plans