← All patternsDP on Two Strings · template
Pattern · Dynamic Programming
DP on Two Strings
dp[i][j] answers the question for the first i characters of one string and the first j of the other.
Time O(m × n) · Space O(m × n), or O(n) with two rows
Taught in Module 31: DP on Strings and Sequences
Think of it like this
Comparing two drafts of an essay line by line, filling a table of how similar every pair of prefixes is.
Clues that point here
- → Two strings or sequences compared
- → Longest common subsequence
- → Edit distance (insert, delete, replace)
- → Interleaving, distinct subsequences
Not this pattern when
- ✕ Only one string is involved (1D or interval DP)
The template
A skeleton to adapt. The parts in comments are what changes from problem to problem.
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]; // LCS lengthCommon versions
- Longest common subsequence
- Edit distance
- Distinct subsequences
- Interleaving string
- Shortest common supersequence
Practice problems with this pattern
31.3Longest Common SubsequenceMediummain pattern31.4Edit DistanceMediummain pattern31.7Distinct SubsequencesHardmain pattern31.8Interleaving StringMediummain pattern31.9Wildcard MatchingHardmain pattern31.5Longest Palindromic SubsequenceMediumalso uses it