Have you ever typed "recieve" and seen your phone suggest "receive"? Or used git diff and seen exactly which lines changed between two versions of a file?
Behind both of these is the same question: how similar are two strings, and how do they line up?
Answering that question efficiently is the job of DP on Strings.
DP on strings is 2D dynamic programming where dp[i][j] stores the answer for the first i characters of one string and the first j characters of another string.
The two classic problems are:
LCS → Longest Common Subsequence: what do two strings have in common?
Edit Distance → Minimum operations to turn one string into anotherOnce you understand these two, a whole family of string problems (longest common substring, palindromic subsequence, minimum insertions, and more) becomes small variations of the same table.
This chapter uses the 2D table and padding ideas from the 2D Dynamic Programming chapter, so make sure you're comfortable with those first.
Subsequence vs Substring
Before we start, let's be very clear about these two words, because they lead to different problems.
String: "abcde"
Substring → contiguous characters : "bcd", "ab", "e"
Subsequence → keep order, may skip chars : "ace", "bd", "abde""ace" is a subsequence of "abcde" (we skipped b and d), but it is not a substring. Every substring is a subsequence, but not every subsequence is a substring.
This is the same difference as subarray vs subsequence in the 1D DP chapter.
Longest Common Subsequence (LCS)
Given two strings, find the length of the longest subsequence that appears in both.
a = "abcde"
b = "ace"
Common subsequences: "a", "c", "e", "ac", "ae", "ce", "ace"
Longest: "ace"
Answer: 3Why Brute Force Is Too Slow
A string of length n has 2ⁿ subsequences (each character is either kept or skipped). Checking all of them against the other string is hopeless for strings of even 40 or 50 characters.
Compare the Last Characters
Here's the key insight. Look at the last character of each string.
Case 1: they match. Then that character can be the last character of the LCS. We add 1 and solve for both strings without their last character.
a = "abcd e"
b = "ac e"
↑ match → LCS = 1 + LCS("abcd", "ac")Case 2: they don't match. Then at least one of them is not part of the LCS. We try dropping each one and keep the better result.
a = "abc d"
b = "ac"
LCS = max( LCS("abc", "ac"), ← drop last char of a
LCS("abcd", "a") ) ← drop last char of bEach call works on prefixes of the two strings, and the same pairs of prefixes come up again and again. That's DP.
The DP Formulation
State : dp[i][j] = LCS length of a[0..i-1] and b[0..j-1]
(the first i chars of a, first j chars of b)
Recurrence : if a[i-1] == b[j-1]:
dp[i][j] = 1 + dp[i-1][j-1]
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
Base cases : dp[0][j] = 0, dp[i][0] = 0
(an empty string has nothing in common with anything)
Answer : dp[n][m]Using i to mean "the first i characters" means character i is at a.charAt(i - 1). Row 0 and column 0 represent empty strings, so the table is padded with zeros. That's the same padding trick from the Maximal Square problem.
Filling the LCS Table
For a = "abcde" (rows) and b = "ace" (columns):
"" a c e
"" 0 0 0 0
a 0 1 1 1
b 0 1 1 1
c 0 1 2 2
d 0 1 2 2
e 0 1 2 3 ← answerHow to read a cell:
Characters match → take the diagonal value (up-left) and add 1.
Characters differ → take the larger of the cell above and the cell to the left.
dp[3][2] (a: "abc", b: "ac") → 'c' == 'c' → 1 + dp[2][1] = 1 + 1 = 2
dp[4][3] (a: "abcd", b: "ace") → 'd' != 'e' → max(dp[3][3], dp[4][2]) = max(2, 2) = 2
dp[5][3] (a: "abcde", b: "ace") → 'e' == 'e' → 1 + dp[4][2] = 1 + 2 = 3Printing the Actual LCS
Just like knapsack and minimum path sum, we can walk backwards through the table to recover the actual subsequence:
Start at dp[n][m].
If a[i-1] == b[j-1]:
this character is in the LCS → record it, move diagonally (i-1, j-1)
Else:
move toward the bigger neighbour (up or left)
Stop when i == 0 or j == 0. Reverse the recorded characters.static String lcs(String a, String b) {
int n = a.length();
int m = b.length();
int[][] dp = new int[n + 1][m + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (a.charAt(i - 1) == b.charAt(j - 1)) {
dp[i][j] = 1 + dp[i - 1][j - 1];
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
// Walk back to build the LCS string
StringBuilder sb = new StringBuilder();
int i = n;
int j = m;
while (i > 0 && j > 0) {
if (a.charAt(i - 1) == b.charAt(j - 1)) {
sb.append(a.charAt(i - 1));
i--;
j--;
} else if (dp[i - 1][j] >= dp[i][j - 1]) {
i--;
} else {
j--;
}
}
return sb.reverse().toString();
}For "ABCBDAB" and "BDCABA", this returns "BCBA" (length 4).
Note that two strings can have more than one LCS of the same length. For this pair, "BDAB" and "BCAB" are also valid answers. Which one you get depends on how you break ties (>= vs >) when walking back. The length is always the same.
Complexity: n × m states, O(1) work each:
Time → O(n × m)
Space → O(n × m)Space Optimization: Two Rows
Each row of the LCS table only reads the row above it (above and diagonal) and the current row (left). So if you only need the length, two 1D arrays are enough:
static int lcsLength(String a, String b) {
int m = b.length();
int[] prev = new int[m + 1]; // row i - 1
int[] curr = new int[m + 1]; // row i
for (int i = 1; i <= a.length(); i++) {
for (int j = 1; j <= m; j++) {
if (a.charAt(i - 1) == b.charAt(j - 1)) {
curr[j] = 1 + prev[j - 1];
} else {
curr[j] = Math.max(prev[j], curr[j - 1]);
}
}
int[] temp = prev; // the current row becomes the previous row
prev = curr;
curr = temp;
}
return prev[m];
}Space drops to O(m). As always, compressing the table means you can't print the subsequence anymore.
Is it safe to reuse the old prev array as the next curr without clearing it? Yes. curr[0] is always 0 (never written), and every other curr[j] is overwritten before it is read in the next row.
Longest Common Substring
What if we want the longest common substring (contiguous) instead?
a = "abcdxyz"
b = "xyzabcd"
Longest common substring: "abcd"
Answer: 4Only one thing changes. When the characters don't match, a substring can't skip characters, so the common run is broken and the value resets to 0:
State : dp[i][j] = length of the longest common substring
that ENDS at a[i-1] and b[j-1]
Recurrence : if a[i-1] == b[j-1]: dp[i][j] = 1 + dp[i-1][j-1]
else: dp[i][j] = 0
Answer : the MAXIMUM value anywhere in the tablestatic int longestCommonSubstring(String a, String b) {
int n = a.length();
int m = b.length();
int[][] dp = new int[n + 1][m + 1];
int best = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (a.charAt(i - 1) == b.charAt(j - 1)) {
dp[i][j] = 1 + dp[i - 1][j - 1];
best = Math.max(best, dp[i][j]);
}
// else dp[i][j] stays 0: the substring is broken
}
}
return best;
}This is exactly the "ending-at" idea from the 1D DP chapter (like Maximum Subarray): because the answer can end anywhere, we track the maximum over all cells.
Longest Common Subsequence | Longest Common Substring | |
|---|---|---|
Characters must be contiguous? | No | Yes |
On match |
|
|
On mismatch |
|
|
Answer |
| Max over the whole table |
Edit Distance
Edit Distance (also called Levenshtein distance) is the minimum number of operations needed to convert string a into string b, where each operation is one of:
Insert a character
Delete a character
Replace a characterExample:
a = "horse", b = "ros"
horse → rorse (replace 'h' with 'r')
rorse → rose (delete 'r')
rose → ros (delete 'e')
Answer: 3This is what spell checkers use to find words that are "close" to what you typed.
Compare the Last Characters Again
Let dp[i][j] be the edit distance between the first i characters of a and the first j characters of b.
If the last characters match, they're already fine. No operation is needed for them:
dp[i][j] = dp[i-1][j-1]If they don't match, we must do one operation on the end of a. There are three choices:
Replace a[i-1] with b[j-1] → both last chars now match → 1 + dp[i-1][j-1]
Delete a[i-1] → a loses one char → 1 + dp[i-1][j]
Insert b[j-1] at the end → b's last char is matched → 1 + dp[i][j-1]
dp[i][j] = 1 + min(replace, delete, insert)Base Cases Are Not Zero This Time
Converting a string to an empty string, or an empty string to a string, has a real cost:
dp[i][0] = i (delete all i characters)
dp[0][j] = j (insert all j characters)This is the most common mistake in edit distance. If you leave the first row and column as zeros, every answer will be too small.
Filling the Table
For a = "horse" (rows) and b = "ros" (columns):
"" r o s
"" 0 1 2 3
h 1 1 2 3
o 2 2 1 2
r 3 2 2 2
s 4 3 3 2
e 5 4 4 3 ← answerA few cells:
dp[1][1] ('h' vs 'r', differ): 1 + min(dp[0][0], dp[0][1], dp[1][0]) = 1 + min(0, 1, 1) = 1
dp[2][2] ('o' vs 'o', match) : dp[1][1] = 1
dp[4][3] ('s' vs 's', match) : dp[3][2] = 2
dp[5][3] ('e' vs 's', differ): 1 + min(dp[4][2], dp[4][3], dp[5][2]) = 1 + min(3, 2, 4) = 3static int editDistance(String a, String b) {
int n = a.length();
int m = b.length();
int[][] dp = new int[n + 1][m + 1];
for (int i = 0; i <= n; i++) {
dp[i][0] = i; // delete all i characters
}
for (int j = 0; j <= m; j++) {
dp[0][j] = j; // insert all j characters
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (a.charAt(i - 1) == b.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1]; // no cost
} 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[n][m];
}Complexity: Time O(n × m), Space O(n × m), reducible to O(m) with two rows (just like LCS).
A second example: "intention" → "execution" has edit distance 5.
Longest Palindromic Subsequence
A palindrome reads the same forwards and backwards. Find the length of the longest palindromic subsequence of a string.
s = "bbbab"
Longest palindromic subsequence: "bbbb"
Answer: 4Here's a beautiful trick: a palindrome is the same when reversed. So the longest palindromic subsequence of s is exactly the LCS of s and reverse(s).
s = "bbbab"
reverse(s) = "babbb"
LCS = "bbbb" → 4static int longestPalindromicSubsequence(String s) {
String reversed = new StringBuilder(s).reverse().toString();
return lcsLength(s, reversed);
}No new DP needed. We just reused LCS.
Bonus: Minimum Insertions to Make a Palindrome
How many characters must you insert (anywhere) to make a string a palindrome?
The characters that are already part of the longest palindromic subsequence can stay. Every other character needs a matching partner inserted on the other side. So:
min insertions = length of s − LPS(s)s = "mbadm"
LPS = "mam" (or "mbm", or "mdm") → length 3
min insertions = 5 − 3 = 2
One result: "mbdadbm" (insert 'd' after 'b', and 'b' before the last 'm')static int minInsertionsForPalindrome(String s) {
return s.length() - longestPalindromicSubsequence(s);
}Complete Java Program
class Main {
// 1. Longest Common Subsequence (length + one actual LCS)
static String lcs(String a, String b) {
int n = a.length();
int m = b.length();
int[][] dp = new int[n + 1][m + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (a.charAt(i - 1) == b.charAt(j - 1)) {
dp[i][j] = 1 + dp[i - 1][j - 1];
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
// Walk back to build the LCS string
StringBuilder sb = new StringBuilder();
int i = n;
int j = m;
while (i > 0 && j > 0) {
if (a.charAt(i - 1) == b.charAt(j - 1)) {
sb.append(a.charAt(i - 1));
i--;
j--;
} else if (dp[i - 1][j] >= dp[i][j - 1]) {
i--;
} else {
j--;
}
}
return sb.reverse().toString();
}
// 2. LCS length with only two rows
static int lcsLength(String a, String b) {
int m = b.length();
int[] prev = new int[m + 1];
int[] curr = new int[m + 1];
for (int i = 1; i <= a.length(); i++) {
for (int j = 1; j <= m; j++) {
if (a.charAt(i - 1) == b.charAt(j - 1)) {
curr[j] = 1 + prev[j - 1];
} else {
curr[j] = Math.max(prev[j], curr[j - 1]);
}
}
int[] temp = prev;
prev = curr;
curr = temp;
}
return prev[m];
}
// 3. Longest Common Substring (contiguous)
static int longestCommonSubstring(String a, String b) {
int n = a.length();
int m = b.length();
int[][] dp = new int[n + 1][m + 1];
int best = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (a.charAt(i - 1) == b.charAt(j - 1)) {
dp[i][j] = 1 + dp[i - 1][j - 1];
best = Math.max(best, dp[i][j]);
}
// else dp[i][j] stays 0: the substring is broken
}
}
return best;
}
// 4. Edit Distance (Levenshtein distance)
static int editDistance(String a, String b) {
int n = a.length();
int m = b.length();
int[][] dp = new int[n + 1][m + 1];
for (int i = 0; i <= n; i++) {
dp[i][0] = i; // delete all i characters
}
for (int j = 0; j <= m; j++) {
dp[0][j] = j; // insert all j characters
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (a.charAt(i - 1) == b.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1]; // no cost
} 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[n][m];
}
// 5. Longest Palindromic Subsequence = LCS(s, reverse(s))
static int longestPalindromicSubsequence(String s) {
String reversed = new StringBuilder(s).reverse().toString();
return lcsLength(s, reversed);
}
// 6. Minimum insertions to make a string a palindrome
static int minInsertionsForPalindrome(String s) {
return s.length() - longestPalindromicSubsequence(s);
}
public static void main(String[] args) {
System.out.println("LCS(\"abcde\", \"ace\") : "
+ lcsLength("abcde", "ace"));
String lcs = lcs("ABCBDAB", "BDCABA");
System.out.println("LCS(\"ABCBDAB\", \"BDCABA\") : "
+ lcs.length() + " -> " + lcs);
System.out.println("Longest common substring : "
+ longestCommonSubstring("abcdxyz", "xyzabcd"));
System.out.println("Edit distance horse -> ros : "
+ editDistance("horse", "ros"));
System.out.println("Edit distance intention -> execution : "
+ editDistance("intention", "execution"));
System.out.println("Longest palindromic subseq : "
+ longestPalindromicSubsequence("bbbab"));
System.out.println("Min insertions for \"mbadm\" : "
+ minInsertionsForPalindrome("mbadm"));
}
}Output:
LCS("abcde", "ace") : 3
LCS("ABCBDAB", "BDCABA") : 4 -> BCBA
Longest common substring : 4
Edit distance horse -> ros : 3
Edit distance intention -> execution : 5
Longest palindromic subseq : 4
Min insertions for "mbadm" : 2The Pattern Behind All String DP
Every problem in this chapter follows the same template:
1. dp[i][j] = answer for a[0..i-1] and b[0..j-1]
2. Table size (n + 1) × (m + 1); row 0 and column 0 mean "empty string"
3. Compare a[i-1] and b[j-1]:
match → usually use the diagonal dp[i-1][j-1]
mismatch → combine above dp[i-1][j], left dp[i][j-1], diagonal
4. Fill row by row, left to right
5. Answer at dp[n][m] (or the max cell, for "ending-at" states)Problem | Base Cases | Match | Mismatch |
|---|---|---|---|
LCS | All 0 |
|
|
Longest Common Substring | All 0 |
|
|
Edit Distance |
|
|
|
Longest Palindromic Subsequence | LCS of | ||
Real-World Uses
Diff tools (
diff,git diff): finding which lines stayed the same between two files is closely related to LCS on lines.Spell checkers and autocorrect: suggest dictionary words with a small edit distance from what you typed.
DNA and protein analysis: biologists compare genetic sequences using alignment algorithms built on the same DP idea.
Plagiarism detection: measure how much text two documents share.
Fuzzy search: find results even when the search term has typos.
Common Mistakes
1. Index confusion
With a padded table, dp[i][j] compares a.charAt(i - 1) and b.charAt(j - 1). Using a.charAt(i) skips the first character and crashes on the last one.
2. Zero base cases in edit distance
Converting "abc" to "" costs 3 deletions, not 0. Initialize the first row and column with j and i.
3. Mixing up subsequence and substring
On a mismatch, LCS takes max(up, left) but longest common substring resets to 0. Using the wrong one gives a wrong answer that still looks reasonable.
4. Expecting a unique LCS
There can be several LCS strings of the same length. If a problem asks for "any one", any of them is correct. Don't hard-code an expected string in your tests unless you also fix the tie-breaking rule.
5. Space-optimizing when you need the string
The two-row version gives only the length. Keep the full table to reconstruct the subsequence or the edit operations.
Practice Problems
Longest Common Subsequence (LeetCode 1143)
Edit Distance (LeetCode 72)
Longest Palindromic Subsequence (LeetCode 516)
Minimum Insertion Steps to Make a String Palindrome (LeetCode 1312)
Delete Operation for Two Strings (LeetCode 583), which uses LCS
Shortest Common Supersequence (LeetCode 1092), which also uses LCS
Distinct Subsequences (LeetCode 115)
Longest Common Substring (GeeksforGeeks)
Wildcard Matching (LeetCode 44) and Regular Expression Matching (LeetCode 10), both advanced
The Main Idea
DP on strings builds a 2D table where dp[i][j] holds the answer for the first i characters of one string and the first j characters of the other.
The key move is always the same: compare the last characters.
LCS
match → 1 + dp[i-1][j-1]
mismatch → max(dp[i-1][j], dp[i][j-1])
Edit Distance
match → dp[i-1][j-1]
mismatch → 1 + min(replace, delete, insert)The complexity for two strings of lengths n and m is:
Time → O(n × m)
Space → O(n × m), or O(m) if you only need the numberWhen a problem compares two strings, or a string with its own reverse, try defining dp[i][j] on prefixes and ask what happens when the last characters match or don't match.
With this chapter, you've covered the core Dynamic Programming patterns: 1D DP, grid DP, knapsack, and string DP. Almost every DP problem you'll meet in placement interviews is built from one of these patterns, or a combination of them.