Preview — Pro guide
You are seeing a portion of this guide. Sign in and upgrade to unlock the full article, quizzes, and interview answers.
DP on Strings: LCS, Edit Distance, and Regex Matching
Master the universal 2D string DP template that unlocks LCS, Edit Distance, Longest Palindromic Subsequence, and Regex Matching. Covers state definitions, space optimization from O(nm) to O(min(n,m)), and the five string DP archetypes that appear most in FAANG interviews.
The Universal String DP Template
Every string DP problem reduces to one mental model: dp[i][j] represents something about the first i characters of s1 and the first j characters of s2. Internalizing this frame before reading the problem statement lets you skip the 'what is the state?' struggle and go directly to 'what does dp[i][j] mean in this problem?'
The key insight that trips up most candidates: dp[i][j] uses 1-indexed positions, but accesses s1[i-1] and s2[j-1]. The first row (i=0) and first column (j=0) represent the empty string — they hold your base cases. Every real character of s1 starts at index 1. Confusing these two index conventions is the single most common source of off-by-one bugs in string DP.
The 2D table has a standard fill order: left-to-right, top-to-bottom (or equivalently, by increasing i and j). This order guarantees that when you compute dp[i][j], the three cells it depends on — dp[i-1][j-1] (diagonal), dp[i-1][j] (above), dp[i][j-1] (left) — are already filled. The transition type determines which of these three neighbors you look at:
- Diagonal (dp[i-1][j-1]): the characters at position i and j 'matched' somehow — reduces both strings simultaneously.
- Above (dp[i-1][j]): something happened to s1[i] alone — you 'consumed' a character from s1.
- Left (dp[i][j-1]): something happened to s2[j] alone — you 'consumed' a character from s2.
Once you see that LCS, Edit Distance, and Distinct Subsequences all decompose into these three directions, the recurrences stop feeling like magic formulas and start feeling like obvious consequences of the state definition. The state definition is the hardest part — everything else is mechanical.
What Interviewers Are Testing in String DP
String DP problems are a FAANG litmus test for pattern recognition under pressure. The interviewer already knows you can look up the LCS formula. What they're testing: (1) Can you independently derive the state definition from the problem statement? (2) Do you know the space optimization trick and when to apply it? (3) Can you recognize when LPS reduces to LCS instead of requiring a separate recurrence?
The answer that impresses: derive the recurrence live, code it with the 1D space optimization by default (not as an afterthought), and explain why the index goes from W to 0 for the rolling array. Most candidates who pass the LC Medium string DP problems have memorized transitions — interviewers detect this by asking why.