Advanced · Module 18 · Lesson 6
String DP
LCS, edit distance, palindromes, and word breaks.
Lesson 110 of 123
1d streakString DP: Longest Common Subsequence & Edit Distance Alignments
String dynamic programming aligns prefixes of two strings S1 (length M) and S2 (length N). In Longest Common Subsequence (LCS), matching characters extend the common sequence: if S1[i-1] == S2[j-1], dp[i][j] = 1 + dp[i-1][j-1]; otherwise we branch on skipping a character from S1 or S2: dp[i][j] = max(dp[i-1][j], dp[i][j-1]). Edit Distance (Levenshtein) extends this by pricing insert, delete, and replace operations.
// Longest Common Subsequence: O(M * N) time, O(N) space
public int longestCommonSubsequence(String text1, String text2) {
int m = text1.length(), n = text2.length();
int[] prev = new int[n + 1];
int[] curr = new int[n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
curr[j] = 1 + prev[j - 1];
} else {
curr[j] = Math.max(prev[j], curr[j - 1]);
}
}
System.arraycopy(curr, 0, prev, 0, n + 1);
}
return prev[n];
}
// Edit Distance: Min operations (insert, delete, replace) to convert word1 to word2
public int minDistance(String word1, String word2) {
int m = word1.length(), n = word2.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 0; i <= m; i++) dp[i][0] = i; // Deleting all chars
for (int j = 0; j <= n; j++) dp[0][j] = j; // Inserting all chars
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1]; // No op needed
} 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];
}Active Recall Checkpoint
In Edit Distance, why is dp[0][j] initialized to j instead of 0?
Show answer & explanation
dp[0][j] represents converting an empty string (length 0) into a string of length j. Transforming an empty string into a j-length string strictly requires j insertion operations.
Use it when
Use String DP for Git diff calculations, spell check suggestions, bioinformatics DNA sequence alignment, and regex wildcard matching.
Reconsider when
For exact substring pattern matching, use KMP or Rabin-Karp (O(M + N)) rather than 2D dynamic programming (O(M × N)).
Cost Model
Complexity & Trade-offs
When to use it
- Optimization, counting, and feasibility with overlapping subproblems.
- Sequence, grid, interval, tree, subset, and digit constraints.
- Replacing exponential recursion with reusable state.
Common mistakes
- Defining a state that lacks information needed by the transition.
- Iterating in an order that reads unresolved or same-round values.
- Optimizing space before proving dependencies.
Practice prompts
- Reproduce the worked String DP example without looking at the trace.
- Change one input condition and explain whether the String DP invariant still holds.
- Implement the approach, derive its cost, and compare it with a straightforward baseline.
Mastery check