# Dynamic Programming on Strings Interview Patterns

Source: https://www.techinterview.org/post/3233466948/dp-string-patterns/
Updated: 2026-04-17 · techinterview.org

## Dynamic Programming on Strings Interview Patterns

String DP problems share a common structure: a 2D table where one dimension indexes into one string and the other indexes into a second string (or the same string in reverse). Once you internalize the table setup and base cases, these problems become mechanical.

## Longest Common Subsequence (LC 1143)

Classic 2D DP. Recurrence: if characters match, `dp[i][j] = dp[i-1][j-1] + 1`; otherwise `dp[i][j] = max(dp[i-1][j], dp[i][j-1])`. The table is (m+1) x (n+1) to handle empty string base cases with zero-filled first row and column.


```
def longest_common_subsequence(text1, text2):
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i-1] == text2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])

    return dp[m][n]

# Space-optimized: O(n) space using rolling rows
def lcs_optimized(text1, text2):
    m, n = len(text1), len(text2)
    prev = [0] * (n + 1)
    curr = [0] * (n + 1)

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i-1] == text2[j-1]:
                curr[j] = prev[j-1] + 1
            else:
                curr[j] = max(prev[j], curr[j-1])
        prev, curr = curr, [0] * (n + 1)

    return prev[n]
```


## Edit Distance (LC 72)

Three operations: insert, delete, replace - each costs 1. When characters match, no operation needed: `dp[i][j] = dp[i-1][j-1]`. When they don't match: `dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])` corresponding to replace, delete from s1, insert into s1.


```
def min_distance(word1, word2):
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    # Base cases: converting to/from empty string
    for i in range(m + 1):
        dp[i][0] = i  # delete all chars from word1
    for j in range(n + 1):
        dp[0][j] = j  # insert all chars of word2

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i-1] == word2[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = 1 + min(
                    dp[i-1][j-1],  # replace
                    dp[i-1][j],    # delete from word1
                    dp[i][j-1]     # insert into word1
                )

    return dp[m][n]
```


## Longest Palindromic Subsequence (LC 516)

Two approaches. Approach 1: LCS of s and reversed(s) - elegant one-liner reduction. Approach 2: expand from single characters outward using a 2D DP table where dp[i][j] = longest palindromic subsequence in s[i..j].


```
# Approach 1: reduce to LCS
def longest_palindromic_subsequence(s):
    return longest_common_subsequence(s, s[::-1])

# Approach 2: interval DP
def lps_interval(s):
    n = len(s)
    dp = [[0] * n for _ in range(n)]

    # Base case: every single character is a palindrome of length 1
    for i in range(n):
        dp[i][i] = 1

    # Fill by increasing interval length
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 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])

    return dp[0][n-1]
```


## Palindrome Partitioning II (LC 132)

Two-phase DP. Phase 1: precompute a 2D boolean table `is_palin[i][j]` to answer palindrome queries in O(1). Phase 2: compute minimum cuts using `cuts[i]` = minimum cuts for s[0..i].


```
def min_cut(s):
    n = len(s)

    # Phase 1: precompute palindrome table
    is_palin = [[False] * n for _ in range(n)]
    for i in range(n):
        is_palin[i][i] = True
    for i in range(n - 1):
        is_palin[i][i+1] = (s[i] == s[i+1])
    for length in range(3, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            is_palin[i][j] = is_palin[i+1][j-1] and s[i] == s[j]

    # Phase 2: minimum cuts
    cuts = list(range(-1, n))  # cuts[i+1] = min cuts for s[0..i]
    for i in range(n):
        for j in range(i + 1):
            if is_palin[j][i]:
                cuts[i+1] = min(cuts[i+1], cuts[j] + 1)

    return cuts[n]
```


## Regular Expression Matching (LC 10)

Hard problem. Rules: '.' matches any single character; '*' matches zero or more of the preceding element. Build a 2D DP table where `dp[i][j]` means pattern p[0..j-1] matches string s[0..i-1]. The '*' case is the tricky part: it either eliminates the preceding pattern char (use zero times) or consumes one char from s (use one or more times).


```
def is_match(s, p):
    m, n = len(s), len(p)
    dp = [[False] * (n + 1) for _ in range(m + 1)]
    dp[0][0] = True  # empty pattern matches empty string

    # Handle patterns like a*, a*b*, a*b*c* matching empty string
    for j in range(2, n + 1):
        if p[j-1] == '*':
            dp[0][j] = dp[0][j-2]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if p[j-1] == '*':
                # Zero occurrences of preceding char: skip p[j-2] and p[j-1]
                dp[i][j] = dp[i][j-2]
                # One or more occurrences: preceding char must match s[i-1]
                if p[j-2] == '.' or p[j-2] == s[i-1]:
                    dp[i][j] = dp[i][j] or dp[i-1][j]
            elif p[j-1] == '.' or p[j-1] == s[i-1]:
                dp[i][j] = dp[i-1][j-1]

    return dp[m][n]
```


## Distinct Subsequences (LC 115)

Count the number of ways to form target t as a subsequence of source s. `dp[i][j]` = number of ways to form t[0..i-1] from s[0..j-1]. If characters match, you can either use s[j-1] to match t[i-1] or skip it: `dp[i][j] = dp[i-1][j-1] + dp[i][j-1]`. If they don't match, you must skip s[j-1]: `dp[i][j] = dp[i][j-1]`.


```
def num_distinct(s, t):
    m, n = len(t), len(s)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    # Base case: empty target can be formed in 1 way (use nothing)
    for j in range(n + 1):
        dp[0][j] = 1

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            dp[i][j] = dp[i][j-1]  # skip s[j-1]
            if t[i-1] == s[j-1]:
                dp[i][j] += dp[i-1][j-1]  # use s[j-1] to match t[i-1]

    return dp[m][n]
```


## Space Optimization: Rolling Two Rows

Most 2D string DP problems only look at the previous row to compute the current row. Rolling two arrays reduces space from O(m*n) to O(n). The LCS example above demonstrates this pattern. Apply it to edit distance and distinct subsequences the same way.


```
# Edit distance with O(n) space
def min_distance_optimized(word1, word2):
    m, n = len(word1), len(word2)
    prev = list(range(n + 1))  # base case: dp[0][j] = j

    for i in range(1, m + 1):
        curr = [i] + [0] * n  # base case: dp[i][0] = i
        for j in range(1, n + 1):
            if word1[i-1] == word2[j-1]:
                curr[j] = prev[j-1]
            else:
                curr[j] = 1 + min(prev[j-1], prev[j], curr[j-1])
        prev = curr

    return prev[n]
```


## Common Pitfalls

- **1-indexed vs 0-indexed offsets:** when the DP table is (m+1) x (n+1), remember that `dp[i][j]` corresponds to `s[i-1]` and `t[j-1]`. Mixing up the offset is the most common source of bugs.

- **Empty string base cases:** always initialize the first row and column explicitly. Forgetting these leads to wrong answers on inputs where one string is empty.

- **Interval DP fill order:** for palindrome problems using interval DP, fill by increasing length, not by row. Getting the fill order wrong produces incorrect results silently.

- **Rolling array diagonal:** when rolling two rows, the diagonal value `dp[i-1][j-1]` needs to be saved before being overwritten. Cache it in a variable at the start of each inner loop iteration.

Meta coding interviews test string DP extensively. See common questions for [Meta interview: string DP and dynamic programming problems](https://www.techinterview.org/post/3233460272/meta-interview-guide-2026-facebook-instagram-whatsapp-engineering/).

Atlassian coding rounds include string DP and edit distance. See patterns for [Atlassian interview: string algorithms and DP problems](https://www.techinterview.org/post/3233459919/atlassian-interview/).

Apple coding rounds test string DP including LCS and edit distance. See patterns for [Apple interview: string dynamic programming problems](https://www.techinterview.org/post/3233460277/apple-interview-guide-2026-ios-systems-hardware-software-integration-and-icloud-architecture/).