DSA: Dynamic Programming on Strings
Solve classic string DP problems: LCS, edit distance, palindromes, pattern matching, and more.
Longest Common Subsequence (LCS)
Find the length of the longest subsequence present in both strings. Characters do not need to be contiguous but must appear in the same relative order.
Longest Common Subsequence
dp[i][j] = LCS length of s1[0..i-1] and s2[0..j-1].
- Match: dp[i][j] = 1 + dp[i-1][j-1] when s1[i-1] == s2[j-1]
- No match: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
- Base case: dp[i][0] = dp[0][j] = 0
- Time: O(m * n), Space: O(m * n) or O(n) with row optimization
Longest Common Subsequence
C++2D DP table: match characters or take the best of skip-either direction.
Longest Common Substring
Unlike LCS, a substring must be contiguous. The DP cell resets to 0 when characters do not match, and the answer is the maximum value seen across the entire table.
Longest Common Substring
dp[i][j] = length of common substring ending at s1[i-1] and s2[j-1].
- Match: dp[i][j] = 1 + dp[i-1][j-1]
- No match: dp[i][j] = 0 (substring must be contiguous, so reset)
- Answer: maximum value across the entire dp table
- Key difference from LCS: no max(skip left, skip up) step
Longest Common Substring
C++Reset dp cell to 0 on mismatch; track maximum across the table.
Longest Palindromic Subsequence
The longest palindromic subsequence of a string equals the LCS of the string and its reverse. This elegant reduction avoids writing a separate DP.
Longest Palindromic Subsequence
LPS(s) = LCS(s, reverse(s)). Reuses the LCS DP directly.
- Reverse s to get rev; then compute LCS(s, rev)
- Any character in both s and rev (same relative order) forms a palindrome
- Minimum insertions to make palindrome = len(s) - LPS(s)
- Time: O(n²), Space: O(n²)
Longest Palindromic Subsequence
C++Reduce to LCS(s, reverse(s)) for a clean one-liner solution.
Longest Palindromic Substring
Find the longest contiguous substring that is a palindrome. The DP tabledp[i][j] stores whethers[i..j] is a palindrome.
Longest Palindromic Substring
Expand by length: single chars and pairs are base cases; longer substrings use dp[i+1][j-1].
- Base: every single character is a palindrome (dp[i][i] = true)
- Base: dp[i][i+1] = true if s[i] == s[i+1]
- Extension: dp[i][j] = true if s[i] == s[j] and dp[i+1][j-1] is true
- Iterate by substring length (len = 2 to n) to ensure dp[i+1][j-1] is computed first
Longest Palindromic Substring
C++Iterate by length to build palindrome table from smaller to larger substrings.
Shortest Common Supersequence
Find the shortest string that has both given strings as subsequences. Length of the SCS equalslen(s1) + len(s2) - LCS(s1, s2).
Shortest Common Supersequence
SCS length = len(s1) + len(s2) - LCS. Build string by tracing the LCS DP table.
- Shared characters (in LCS) appear once in SCS; rest appear separately
- Trace dp table: if chars match, take once; else take from whichever skip gave max
- Relation to Edit Distance: SCS uses LCS; edit distance minimizes insert/delete/replace
- Time: O(m * n), Space: O(m * n)
Shortest Common Supersequence Length
C++Compute LCS length first, then apply the SCS formula.
Edit Distance (Levenshtein Distance)
Find the minimum number of insert, delete, and replace operations needed to convert strings1 intos2.
Edit Distance
dp[i][j] = min operations to convert s1[0..i-1] to s2[0..j-1].
- Match: dp[i][j] = dp[i-1][j-1] (no operation needed)
- Insert: dp[i][j-1] + 1 (insert s2[j-1] into s1)
- Delete: dp[i-1][j] + 1 (delete s1[i-1] from s1)
- Replace: dp[i-1][j-1] + 1 (replace s1[i-1] with s2[j-1])
- No match: dp[i][j] = min(insert, delete, replace)
Edit Distance
C++Three operations: insert, delete, replace. Take minimum at each cell.
Wildcard Pattern Matching
Match a string against a pattern containing ? (matches any single character) and * (matches zero or more of any characters).
Wildcard Matching
dp[i][j] = true if pattern[0..i-1] matches string[0..j-1].
- Exact or ?: dp[i][j] = dp[i-1][j-1] when p[i-1] == s[j-1] or p[i-1] == '?'
- Star matches empty: dp[i][j] = dp[i-1][j]
- Star matches one more: dp[i][j] = dp[i][j-1]
- Star case: dp[i][j] = dp[i-1][j] || dp[i][j-1]
Wildcard Pattern Matching
C++Handle * by either skipping it or using it to consume one more character.
Distinct Subsequences
Count the number of distinct ways to form stringt as a subsequence of strings.
Distinct Subsequences
dp[i][j] = number of ways to form t[0..j-1] from s[0..i-1].
- Base: dp[i][0] = 1 for all i (empty t formed in exactly one way: use nothing)
- No match: dp[i][j] = dp[i-1][j] (skip s[i-1])
- Match: dp[i][j] = dp[i-1][j] + dp[i-1][j-1] (skip or use s[i-1])
- Answer: dp[m][n] where m = len(s), n = len(t)
Distinct Subsequences
C++Count ways to pick characters from s (in order) to spell out t.
String DP Problem Map
All string DP problems share a 2D table over two strings. Recognizing the recurrence pattern is the key skill.
| Problem | dp[i][j] meaning | Match case | No-match case |
|---|---|---|---|
| LCS | LCS length of s1[..i] and s2[..j] | 1 + dp[i-1][j-1] | max(up, left) |
| LCS Substring | Common substr ending at i,j | 1 + dp[i-1][j-1] | 0 (reset) |
| Edit Distance | Min ops to convert s1[..i] to s2[..j] | dp[i-1][j-1] | 1 + min(3 neighbors) |
| Wildcard | p[..i] matches s[..j] | dp[i-1][j-1] | false (or * logic) |
| Distinct Subseq | Ways to form t[..j] from s[..i] | dp[i-1][j] + dp[i-1][j-1] | dp[i-1][j] |
| SCS Length | LCS then formula | same as LCS | same as LCS |
Knowledge Check
1. What is the difference between Longest Common Subsequence and Longest Common Substring?
2. The recurrence for LCS when characters match is:
3. Longest Palindromic Subsequence of string s equals:
4. Edit distance counts the minimum number of which operations?
5. In Edit Distance DP, when s1[i] == s2[j], the cost is:
6. Shortest Common Supersequence length for strings A and B equals:
7. In wildcard matching, the * character matches:
8. Distinct Subsequences dp[i][j] counts: