Stage 1 · Code

Dynamic Programming & Greedy

DP on Strings

Edit distance, longest common subsequence, and palindromes — solved with 2D tables that compare characters pairwise.

10 min readLeetCode Patterns for InterviewsCode

The String DP Framework

String DP problems share a defining trait: the answer depends on comparing prefixes of two strings (or two halves of one string). The recurrence almost always reasons about what happens when the last characters match or differ.

The Core Insight

Every string DP problem reduces to: 'What does dp[i][j] mean, and how does dp[i-1][j-1], dp[i-1][j], and dp[i][j-1] inform it?' Master this question and you've mastered the pattern.

These problems fall into three buckets:

LCS family (edit distance, delete operation for two strings): dp[i][j] = longest common subsequence of prefixes of length i and j.
Palindrome family: dp[i][j] = is substring s[i..j] a palindrome? Or what's the longest palindrome?
Distinct subsequences (count how many times T appears as a subsequence in S): dp[i][j] counts matches for prefixes.

2D Table Method

Draw a table with string A across the columns and string B down the rows. Each cell (i, j) answers the subproblem for A[0..i] and B[0..j]. The recurrence fills from top-left to bottom-right.

Edit distance table for 'CAT' → 'CAR' — dp[i][j] = min edits

The table has dimensions (m+1) × (n+1). The extra row and column represent the empty string prefix. dp[0][j] = j (insert j chars), dp[i][0] = i (delete i chars).

Template

Gogeneric-string-dp-template.go

33 linesLn 1, Col 1Go

The recurrence considers three operations. When characters match, carry forward the diagonal cost. When they differ, pick the cheapest operation and add 1.

Space Optimization

Most 2D string DP only needs the previous row. Replace the full table with two 1D slices (prev and curr). This drops space from O(m·n) to O(n). Only keep the full table if you need to reconstruct the path (e.g., output the edit script).

Edit Distance — LeetCode 72

The canonical string DP problem. Given two strings word1 and word2, return the minimum number of operations (insert, delete, replace) required to convert word1 to word2.

The recurrence: If word1[i-1] == word2[j-1], carry forward dp[i-1][j-1]. Otherwise, 1 + min(dp[i-1][j] (delete), dp[i][j-1] (insert), dp[i-1][j-1] (replace)).

Complexity Spectrum

Brute Force

O(3ⁿ)

Try all operation sequences

Memoized

O(m·n)

2D DP top-down

Tabulation

O(m·n)

Iterative 2D table

Space Optimized

O(m·n)

Time still O(m·n)

Practice Problems

#72Edit DistanceMediumClassic 2D string DP · O(m·n) time · O(m·n) space #5Longest Palindromic SubstringMediumPalindrome DP with 2D boolean table · O(n²) time · O(n²) space #647Palindromic SubstringsMediumCount palindromes with DP · O(n²) time · O(n²) space

Key Points

String DP always adds +1 dimension for the empty prefix.
The recurrence lives at (i-1, j-1), (i-1, j), and (i, j-1) — match, delete, insert.
Palindrome DP fills by substring length, not by row index.
Space can almost always be optimized to O(n) with rolling arrays.
If the problem asks for the actual string (not just length), store a reconstruction path or use the full table.

Mark this lesson complete to store local progress and unlock a cleaner resume path the next time you visit.

Stage 1 · Code

Dynamic Programming & Greedy

DP on Strings

Edit distance, longest common subsequence, and palindromes — solved with 2D tables that compare characters pairwise.

10 min readLeetCode Patterns for InterviewsCode

The String DP Framework

The Core Insight

Every string DP problem reduces to: 'What does dp[i][j] mean, and how does dp[i-1][j-1], dp[i-1][j], and dp[i][j-1] inform it?' Master this question and you've mastered the pattern.

These problems fall into three buckets:

LCS family (edit distance, delete operation for two strings): dp[i][j] = longest common subsequence of prefixes of length i and j.
Palindrome family: dp[i][j] = is substring s[i..j] a palindrome? Or what's the longest palindrome?
Distinct subsequences (count how many times T appears as a subsequence in S): dp[i][j] counts matches for prefixes.

2D Table Method

Draw a table with string A across the columns and string B down the rows. Each cell (i, j) answers the subproblem for A[0..i] and B[0..j]. The recurrence fills from top-left to bottom-right.

Edit distance table for 'CAT' → 'CAR' — dp[i][j] = min edits

The table has dimensions (m+1) × (n+1). The extra row and column represent the empty string prefix. dp[0][j] = j (insert j chars), dp[i][0] = i (delete i chars).

Template

Gogeneric-string-dp-template.go

33 linesLn 1, Col 1Go

The recurrence considers three operations. When characters match, carry forward the diagonal cost. When they differ, pick the cheapest operation and add 1.

Space Optimization

Edit Distance — LeetCode 72

The canonical string DP problem. Given two strings word1 and word2, return the minimum number of operations (insert, delete, replace) required to convert word1 to word2.

The recurrence: If word1[i-1] == word2[j-1], carry forward dp[i-1][j-1]. Otherwise, 1 + min(dp[i-1][j] (delete), dp[i][j-1] (insert), dp[i-1][j-1] (replace)).

Complexity Spectrum

Brute Force

O(3ⁿ)

Try all operation sequences

Memoized

O(m·n)

2D DP top-down

Tabulation

O(m·n)

Iterative 2D table

Space Optimized

O(m·n)

Time still O(m·n)

Practice Problems

Key Points

String DP always adds +1 dimension for the empty prefix.
The recurrence lives at (i-1, j-1), (i-1, j), and (i, j-1) — match, delete, insert.
Palindrome DP fills by substring length, not by row index.
Space can almost always be optimized to O(n) with rolling arrays.
If the problem asks for the actual string (not just length), store a reconstruction path or use the full table.

Mark this lesson complete to store local progress and unlock a cleaner resume path the next time you visit.