String DP

Compare two strings prefix by prefix in a 2D table, or one string against itself, to find subsequences, edit distances and matches.

Overview

Two strings, one table

Most string DP problems compare two strings, A of length m and B of length n. The state is a pair of prefixes: dp[i][j] is the answer for the first i characters of A and the first j characters of B. The table has (m + 1) rows and (n + 1) columns, because row 0 and column 0 stand for the empty prefix. That extra row and column are the base cases, and they are why dp[i][j] reads A[i-1] and B[j-1], not A[i] and B[j].

Every cell asks the same question: do the two last characters match? A match usually extends the diagonal cell. A mismatch combines the cell above and the cell to the left, and sometimes the diagonal too. The problem decides how they combine.

Longest common subsequence — diagonal + 1 — max(above, left) — 0
Edit distance — diagonal — 1 + min(above, left, diagonal) — i and j
Distinct subsequences — above + diagonal — above — dp[i][0] = 1, dp[0][j] = 0
Wildcard matching — diagonal — false, unless the pattern char is * — see the section below

Every cell costs O(1), so all of these run in O(mn) time. Each row reads only the row above it, so two rows are enough and the space drops to O(min(m, n)) if you put the shorter string on the columns.

Longest common subsequence, traced

A subsequence keeps characters in order but may skip some. The longest common subsequence (LCS) of two strings is the longest sequence that is a subsequence of both. dp[i][j] is the LCS length of the two prefixes. On a match, the last characters pair up and the LCS grows by one from the diagonal. On a mismatch, one of the two last characters is not in the answer, so drop the one that costs less: the larger of the cell above and the cell to the left.

Here is the full table for A = 'abcb' (rows) and B = 'bdcab' (columns). Bold cells are matches.

'' — 0 — 0 — 0 — 0 — 0 — 0
a — 0 — 0 — 0 — 0 — 1 — 1
b — 0 — 1 — 1 — 1 — 1 — 2
c — 0 — 1 — 1 — 2 — 2 — 2
b — 0 — 1 — 1 — 2 — 2 — 3

The answer is 3 ('bcb'). Reading a row from left to right, each cell needs only the row above and the cell just filled, which is why two rows suffice. The Unix diff tool is built on this problem: its central algorithm finds the longest common subsequence of lines, and everything outside it is reported as a change.

Edit distance: three moves at every mismatch

The edit distance (Levenshtein distance) between a source and a target is the fewest single-character edits that turn one into the other: insert a character, delete one, or replace one. dp[i][j] is the distance from the first i source characters to the first j target characters. The base cases are not zero: turning i characters into the empty string takes i deletions, and turning the empty string into j characters takes j insertions.

The direction a value comes from tells you which edit it is. Naming these is what shows you understand the table.

Diagonal, same value — Match — The last characters agree, so nothing is needed
Diagonal + 1 — Replace — Turn A[i-1] into B[j-1]
Above + 1 — Delete — Remove A[i-1], then the first i-1 source characters must become the first j target characters
Left + 1 — Insert — Add B[j-1] to the end, then the first i source characters must become the first j-1 target characters

Row by row for source 'cat' and target 'cuts', each cell is the minimum of the three moves.

'' — 0 1 2 3 4 — j insertions to build a prefix from nothing
c — 1 0 1 2 3 — 'c' matches 'c' for free, then insertions
a — 2 1 1 2 3 — 'a' vs 'u' is a replace on top of the diagonal 0
t — 3 2 2 1 2 — 't' matches 't' (diagonal 1), then 's' is one insertion

The answer is 2. No known algorithm does much better than O(mn) in the worst case: Backurs and Indyk showed in 2015 that an O(n^(2-ε)) algorithm for edit distance would contradict the Strong Exponential Time Hypothesis.

One string against itself: substrings by length

Palindrome problems compare a string with itself. The state changes shape: dp[i][j] is the answer for the substring from index i to index j, not for a pair of prefixes. The longest palindromic subsequence (LPS) of s[i..j] is dp[i+1][j-1] + 2 when s[i] and s[j] are equal, and otherwise the larger of dp[i+1][j] and dp[i][j-1].

A cell now reads cells with a larger i or a smaller j, so a plain top-to-bottom loop reads empty cells. Fill by substring length instead, shortest first, or run i from the last index down to 0.

For s = 'abca', by length.

a, b, c, a — 1 each
ab, bc, ca — no — the single characters — 1
abc — no — max(dp of bc, dp of ab) — 1
bca — no — max(dp of ca, dp of bc) — 1
abca — yes, a and a — dp of bc + 2 — 3

The answer is 3 ('aba' or 'aca'). A second route to the same number: the LPS length of s equals the LCS length of s and its reverse. Checking that on 'abca' against 'acba' also gives 3.

Counting instead of optimizing: distinct subsequences

The same table can count. Distinct subsequences asks how many ways t appears as a subsequence of s, counting different index choices separately. dp[i][j] is the number of ways to build the first j characters of t from the first i characters of s. Every cell inherits the ways that skip s[i-1] (the cell above). If s[i-1] equals t[j-1], it also adds the ways that use it (the diagonal). The base cases are dp[i][0] = 1, because the empty t can be built exactly one way, and dp[0][j] = 0 for j > 0.

Here s = 'abab' is on the rows and t = 'ab' on the columns.

'' — 1 — 0 — 0
a — 1 — 1 — 0
b — 1 — 1 — 1
a — 1 — 2 — 1
b — 1 — 2 — 3

The answer is 3: the 'a' at index 0 or 2 pairs with a later 'b', which gives the pairs (0,1), (0,3) and (2,3). Counting tables grow fast, so many problems ask for the answer modulo a large prime; apply the modulo at every cell.

One index is enough for Word Break and Decode Ways

Some string problems have one string and a dictionary or a code, and the state is a single prefix. In Word Break, dp[i] is true when the first i characters can be split into dictionary words. dp[i] is true if some earlier split point j has dp[j] true and s[j:i] is a word. In Decode Ways, dp[i] counts the decodings of the first i digits: add dp[i-1] if the last digit is 1 to 9, and add dp[i-2] if the last two digits form a number from 10 to 26.

Here is Word Break on s = 'catsand' with the words cat, cats, and, sand.

0 — '' — base case — true
1 — c — none — false
2 — ca — none — false
3 — cat — j = 0 (cat) — true
4 — cats — j = 0 (cats) — true
5 — catsa — none — false
6 — catsan — none — false
7 — catsand — j = 3 (sand), j = 4 (and) — true

The plain Word Break tries every split point j for each cell, and hashing the substring s[j:i] costs its length, so the worst case is O(n³). Looping over the dictionary's distinct word lengths instead of every j cuts it to O(n × L × number of lengths) for a maximum word length L, because a substring longer than L is never a word. Decode Ways reads only two earlier cells, so it is O(n) time and O(1) space.

Wildcard matching: the star has two choices

Wildcard matching asks whether a string s matches a pattern p where ? stands for any one character and * stands for any run of characters, including none. dp[i][j] is true when the first i characters of s match the first j characters of p. The base cases are dp[0][0] = true and dp[0][j] = true only while p is all stars up to j.

A letter — it equals s[i-1] and dp[i-1][j-1]
? — dp[i-1][j-1]
* — dp[i][j-1] (the star matches nothing) or dp[i-1][j] (the star also takes s[i-1])

The star row is the whole trick: 'matches nothing' moves left, 'takes one more character' moves up and stays on the same star. Together they let a star swallow any number of characters without a third loop.

Cutting space and rebuilding the answer

Each row of a two-string table reads only the row above, so keep two rows, or one row updated with care. Space becomes O(min(m, n)) when the shorter string is on the columns. That trick loses the ability to walk back through the table. If you need the LCS itself or the list of edits, keep the full table and trace backward from the bottom-right cell.

The walk visits at most m + n cells, so reconstruction costs O(m + n) on top of the table. The characters come out in reverse order; reverse them at the end.

What you will be able to do

Define dp[i][j] for a pair of prefixes, and say why the table has an extra row and column.
Fill LCS, edit distance and distinct-subsequence tables by hand on a tiny input.
Name the edit each neighbor stands for in an edit distance table.
Pick the fill order for substring DP and for prefix DP.
Cut the table to two rows, and know when you must keep it whole.

When to use it

The question compares two strings: a common subsequence, a distance, whether one contains the other as a subsequence
The question is about palindromes inside one string: the longest palindromic subsequence or substring, the fewest insertions to make a palindrome
The question counts ways to form one string from another, or ways to decode or split a string
A string must be split into dictionary words (Word Break)
A pattern with wildcards must match a string
A brute-force recursion over the two strings repeats the same prefix pairs

More Coding & DSA topics

Start free on Cariara · Coding problems · System design studio