Dynamic Programming on Strings Interview Patterns

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.

Atlassian coding rounds include string DP and edit distance. See patterns for Atlassian interview: string algorithms and DP problems.

Apple coding rounds test string DP including LCS and edit distance. See patterns for Apple interview: string dynamic programming problems.