Skip to main content

Pattern 8: String DP (LCS/Edit Distance)

The Alignment Pattern: Compare two sequences character by character. State is dp[i][j] = answer for first i chars of string1 and first j chars of string2.

The Core Pattern​

THE MENTAL MODEL

Imagine aligning two DNA sequences to find the longest match:

  1. Compare character by character from two strings
  2. At each position (i, j), track best solution using first i chars of string1 and first j chars of string2
  3. Make decisions: match, skip from string1, or skip from string2
  4. Build up from empty strings to full strings
  5. Final answer at dp[m][n] where m, n are string lengths

This is String DP.

Pattern Recognition​

WHEN YOU SEE THIS PATTERN

Keywords: "longest common subsequence", "edit distance", "alignment", "two strings", "transform"

Structure:

  • Two sequences to compare
  • Answer depends on matching or skipping characters
  • Need 2D state: one dimension per string

State:

  • dp[i][j] = "best answer using first i chars of s1 and first j chars of s2"

Transitions: Usually 2-3 options

  • If s1[i-1] == s2[j-1]: match them
  • Skip from s1: dp[i-1][j]
  • Skip from s2: dp[i][j-1]

Common Problems​

  • Longest Common Subsequence (LCS)
  • Edit Distance
  • Delete Operation for Two Strings
  • Minimum ASCII Delete Sum
  • Distinct Subsequences
  • Interleaving String

(Example problems will be added here)