Dynamic Programming on Strings: Edit Distance, Longest Common Subsequence, and Palindrome Problems (2025)

Why DP on Strings?

String DP problems have a recognizable structure: two strings of lengths m and n, where the answer depends on the relationship between characters at each position. The state is almost always dp[i][j] representing some property of s1[:i] and s2[:j] (or s[:i] and s[:j] for single-string problems). The recurrence follows from: (a) characters match: dp[i][j] depends on dp[i-1][j-1]; (b) characters don’t match: dp[i][j] = min/max of dp[i-1][j], dp[i][j-1], dp[i-1][j-1] with some cost. Recognizing these patterns lets you derive the recurrence from first principles rather than memorizing solutions.

Edit Distance (LC 72)

Minimum operations (insert, delete, replace) to convert s1 to s2. dp[i][j] = edit distance between s1[:i] and s2[:j]. Base cases: dp[0][j] = j (insert j characters); dp[i][0] = i (delete i characters). Recurrence: if s1[i-1] == s2[j-1]: dp[i][j] = dp[i-1][j-1] (no operation needed). Else: dp[i][j] = 1 + min(dp[i-1][j-1] (replace), dp[i-1][j] (delete from s1), dp[i][j-1] (insert into s1)).

def min_distance(s1, s2):
    m, n = len(s1), len(s2)
    dp = list(range(n+1))  # space-optimized: 1D array
    for i in range(1, m+1):
        prev = dp[0]
        dp[0] = i
        for j in range(1, n+1):
            temp = dp[j]
            if s1[i-1] == s2[j-1]:
                dp[j] = prev
            else:
                dp[j] = 1 + min(prev, dp[j], dp[j-1])
            prev = temp
    return dp[n]

Space optimization: at any row i, dp[i][j] only depends on dp[i-1][j-1], dp[i-1][j], dp[i][j-1] — the previous row and current row. Store only one 1D array, updated left to right, tracking prev = dp[i-1][j-1]. O(n) space instead of O(mn).

Longest Common Subsequence (LC 1143)

Length of the longest subsequence common to both strings. dp[i][j] = LCS of s1[:i] and s2[:j]. If s1[i-1] == s2[j-1]: dp[i][j] = dp[i-1][j-1] + 1. Else: dp[i][j] = max(dp[i-1][j], dp[i][j-1]). O(mn) time and space. Space-optimize to O(n) by the same 1D rolling array technique. LCS variants: Longest Common Substring (contiguous): dp[i][j] = dp[i-1][j-1] + 1 if characters match, else 0. Track the global maximum. Shortest Common Supersequence (LC 1092): SCS = m + n – LCS (add LCS once instead of twice). Print the supersequence by backtracking the DP table.

Palindrome DP Problems

Palindrome check: dp[i][j] = True if s[i:j+1] is a palindrome. dp[i][i] = True; dp[i][i+1] = s[i]==s[i+1]. dp[i][j] = s[i]==s[j] AND dp[i+1][j-1]. Fill diagonally (length 2, 3, …, n). Longest Palindromic Substring (LC 5): find the longest contiguous palindrome. O(n^2) DP or Manacher’s algorithm in O(n). Manacher’s key idea: use previously computed palindrome radii to avoid re-expanding known palindromes. Longest Palindromic Subsequence (LC 516): dp[i][j] = length of longest palindromic subsequence in s[i:j+1]. If s[i] == s[j]: dp[i][j] = dp[i+1][j-1] + 2. Else: dp[i][j] = max(dp[i+1][j], dp[i][j-1]). Minimum Insertions to Make String Palindrome (LC 1312): answer = n – longest palindromic subsequence. Adding n – LPS characters creates a palindrome.

Distinct Subsequences and Interleaving

Distinct Subsequences (LC 115): count the number of times s2 appears as a subsequence in s1. dp[i][j] = number of ways to form s2[:j] from s1[:i]. If s1[i-1] == s2[j-1]: dp[i][j] = dp[i-1][j-1] + dp[i-1][j] (use the match + skip it). Else: dp[i][j] = dp[i-1][j] (must skip s1[i-1]). Interleaving String (LC 97): whether s3 is formed by interleaving s1 and s2. dp[i][j] = True if s3[:i+j] can be formed from s1[:i] and s2[:j]. dp[i][j] = (dp[i-1][j] AND s1[i-1]==s3[i+j-1]) OR (dp[i][j-1] AND s2[j-1]==s3[i+j-1]). These two are the canonical “which subsequence/interleaving is valid” patterns — recognize the 2D dp[i][j] = property of first i chars of s1 and first j chars of s2.

{“@context”:”https://schema.org”,”@type”:”FAQPage”,”mainEntity”:[{“@type”:”Question”,”name”:”What is the recurrence for edit distance (Levenshtein distance)?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”dp[i][j] = edit distance between s1[:i] and s2[:j]. Base cases: dp[0][j] = j, dp[i][0] = i. Recurrence: if s1[i-1] == s2[j-1]: dp[i][j] = dp[i-1][j-1] (free). Else: dp[i][j] = 1 + min(dp[i-1][j-1] for replace, dp[i-1][j] for delete from s1, dp[i][j-1] for insert into s1). Can be space-optimized to O(n) using a 1D rolling array.”}},{“@type”:”Question”,”name”:”What is the difference between Longest Common Subsequence and Longest Common Substring?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”LCS (subsequence) allows non-contiguous characters: dp[i][j] = dp[i-1][j-1] + 1 if characters match, else max(dp[i-1][j], dp[i][j-1]). LCS (substring) requires contiguous characters: dp[i][j] = dp[i-1][j-1] + 1 if characters match, else 0. Track the global maximum separately. LCS subsequence is O(mn) in both time and space; LCS substring is the same but the DP values represent the current run length.”}},{“@type”:”Question”,”name”:”How do you find the longest palindromic subsequence?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”dp[i][j] = length of the longest palindromic subsequence in s[i:j+1]. Fill diagonally. dp[i][i] = 1. If s[i] == s[j]: dp[i][j] = dp[i+1][j-1] + 2. Else: dp[i][j] = max(dp[i+1][j], dp[i][j-1]). The answer is dp[0][n-1]. Key insight: minimum insertions to make a palindrome = n – dp[0][n-1], since we add characters around the existing palindromic subsequence.”}},{“@type”:”Question”,”name”:”How do you count distinct subsequences of s2 in s1 (LC 115)?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”dp[i][j] = number of ways to form s2[:j] using s1[:i]. If s1[i-1] == s2[j-1]: dp[i][j] = dp[i-1][j-1] (use this match) + dp[i-1][j] (skip s1[i-1], use a previous match). Else: dp[i][j] = dp[i-1][j] (must skip s1[i-1]). Base cases: dp[i][0] = 1 (empty s2 is always a subsequence), dp[0][j>0] = 0.”}},{“@type”:”Question”,”name”:”How do you space-optimize 2D string DP to O(n)?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Most 2D string DP only looks at dp[i-1][j-1], dp[i-1][j], and dp[i][j-1] — the previous row and the current row. Store one 1D array of length n+1. Update left to right. Track prev = the value of dp[i-1][j-1] (diagonal) separately, since dp[j-1] will be overwritten before you need the diagonal value. This pattern applies to edit distance, LCS, and interleaving string.”}}]}