Advanced

String DP

String DP problems combine character-by-character processing with dynamic programming. These are among the hardest interview problems, but they all follow predictable patterns once you learn to recognize them.

Problem 1: Longest Palindromic Substring

Problem: Given a string s, find the longest substring that is a palindrome.

State: dp[i][j] = True if s[i..j] is a palindrome.

Recurrence: dp[i][j] = (s[i] == s[j]) and dp[i+1][j-1] (outer chars match and inner substring is a palindrome).

# Brute force: O(n^3) - check every substring
def longest_palindrome_brute(s):
    def is_palindrome(sub):
        return sub == sub[::-1]
    best = ""
    for i in range(len(s)):
        for j in range(i, len(s)):
            if is_palindrome(s[i:j+1]) and j - i + 1 > len(best):
                best = s[i:j+1]
    return best

# DP tabulation: O(n^2) time, O(n^2) space
def longest_palindrome_dp(s):
    n = len(s)
    if n < 2:
        return s
    dp = [[False] * n for _ in range(n)]
    start, max_len = 0, 1

    # Every single character is a palindrome
    for i in range(n):
        dp[i][i] = True

    # Check substrings of length 2+
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j]:
                if length == 2 or dp[i+1][j-1]:
                    dp[i][j] = True
                    if length > max_len:
                        start = i
                        max_len = length
    return s[start:start + max_len]

# Expand around center: O(n^2) time, O(1) space (optimal for this problem)
def longest_palindrome_expand(s):
    def expand(left, right):
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return s[left+1:right]

    result = ""
    for i in range(len(s)):
        # Odd length palindromes
        odd = expand(i, i)
        if len(odd) > len(result):
            result = odd
        # Even length palindromes
        even = expand(i, i + 1)
        if len(even) > len(result):
            result = even
    return result

# Test: longest_palindrome_expand("babad") = "bab" (or "aba")
# Test: longest_palindrome_expand("cbbd") = "bb"

Problem 2: Word Break

Problem: Given a string s and a dictionary of words, determine if s can be segmented into a space-separated sequence of dictionary words.

State: dp[i] = True if s[0..i-1] can be segmented using dictionary words.

Recurrence: dp[i] = True if there exists j < i such that dp[j] is True and s[j..i-1] is in the dictionary.

# Brute force: O(2^n) - try every possible segmentation
def word_break_brute(s, word_dict, start=0):
    if start == len(s):
        return True
    for end in range(start + 1, len(s) + 1):
        if s[start:end] in word_dict and word_break_brute(s, word_dict, end):
            return True
    return False

# Memoization: O(n^2 * k) time where k = avg word length for hashing
def word_break_memo(s, word_dict):
    word_set = set(word_dict)
    memo = {}
    def dp(start):
        if start == len(s):
            return True
        if start in memo:
            return memo[start]
        for end in range(start + 1, len(s) + 1):
            if s[start:end] in word_set and dp(end):
                memo[start] = True
                return True
        memo[start] = False
        return False
    return dp(0)

# Tabulation: O(n^2) time, O(n) space
def word_break_tab(s, word_dict):
    word_set = set(word_dict)
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True  # Empty string is always valid

    for i in range(1, n + 1):
        for j in range(i):
            if dp[j] and s[j:i] in word_set:
                dp[i] = True
                break
    return dp[n]

# Test: word_break_tab("leetcode", ["leet", "code"]) = True
# Test: word_break_tab("applepenapple", ["apple", "pen"]) = True
# Test: word_break_tab("catsandog", ["cats", "dog", "sand", "and", "cat"]) = False
💡
Optimization tip: For word break, you can limit the inner loop to only check substrings whose length matches a word in the dictionary. Precompute the set of word lengths to avoid checking impossible splits.

Problem 3: Regular Expression Matching

Problem: Implement regular expression matching with '.' (matches any single character) and '*' (matches zero or more of the preceding element). The matching should cover the entire input string.

State: dp[i][j] = True if s[0..i-1] matches p[0..j-1].

# Brute force / Memoization: O(m*n) time
def regex_match(s, p):
    memo = {}
    def dp(i, j):
        if (i, j) in memo:
            return memo[(i, j)]
        if j == len(p):
            result = (i == len(s))
        elif j + 1 < len(p) and p[j+1] == '*':
            # '*' pattern: zero matches OR one match + continue
            result = (dp(i, j + 2) or  # zero matches
                     (i < len(s) and (p[j] == '.' or s[i] == p[j]) and dp(i + 1, j)))
        elif i < len(s) and (p[j] == '.' or s[i] == p[j]):
            result = dp(i + 1, j + 1)
        else:
            result = False
        memo[(i, j)] = result
        return result
    return dp(0, 0)

# Tabulation: O(m*n) time, O(m*n) space
def regex_match_tab(s, p):
    m, n = len(s), len(p)
    dp = [[False] * (n + 1) for _ in range(m + 1)]
    dp[0][0] = True

    # Handle patterns like a*, a*b*, a*b*c* that can match 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
                dp[i][j] = dp[i][j-2]
                # One or more: if current char matches preceding pattern char
                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]

# Test: regex_match_tab("aa", "a") = False
# Test: regex_match_tab("aa", "a*") = True
# Test: regex_match_tab("aab", "c*a*b") = True (c* matches zero c's)

Problem 4: Interleaving String

Problem: Given strings s1, s2, and s3, determine if s3 is formed by interleaving s1 and s2. An interleaving preserves the relative order of characters from both strings.

State: dp[i][j] = True if s3[0..i+j-1] can be formed by interleaving s1[0..i-1] and s2[0..j-1].

# Memoization: O(m*n) time
def interleave_memo(s1, s2, s3):
    if len(s1) + len(s2) != len(s3):
        return False
    memo = {}
    def dp(i, j):
        if i == len(s1) and j == len(s2):
            return True
        if (i, j) in memo:
            return memo[(i, j)]
        k = i + j  # Position in s3
        result = False
        if i < len(s1) and s1[i] == s3[k]:
            result = dp(i + 1, j)
        if not result and j < len(s2) and s2[j] == s3[k]:
            result = dp(i, j + 1)
        memo[(i, j)] = result
        return result
    return dp(0, 0)

# Tabulation: O(m*n) time, O(n) space
def interleave_tab(s1, s2, s3):
    m, n = len(s1), len(s2)
    if m + n != len(s3):
        return False
    dp = [False] * (n + 1)
    for i in range(m + 1):
        for j in range(n + 1):
            k = i + j
            if i == 0 and j == 0:
                dp[j] = True
            elif i == 0:
                dp[j] = dp[j-1] and s2[j-1] == s3[k-1]
            elif j == 0:
                dp[j] = dp[j] and s1[i-1] == s3[k-1]
            else:
                dp[j] = ((dp[j] and s1[i-1] == s3[k-1]) or
                         (dp[j-1] and s2[j-1] == s3[k-1]))
    return dp[n]

# Test: interleave_tab("aabcc", "dbbca", "aadbbcbcac") = True
# Test: interleave_tab("aabcc", "dbbca", "aadbbbaccc") = False

Problem 5: Distinct Subsequences

Problem: Given strings s and t, count the number of distinct subsequences of s that equal t.

State: dp[i][j] = number of ways to form t[0..j-1] from s[0..i-1].

Recurrence: If s[i-1] == t[j-1], dp[i][j] = dp[i-1][j-1] + dp[i-1][j] (use this char or skip it). Else dp[i][j] = dp[i-1][j] (must skip it).

# Brute force: O(2^m) where m = len(s)
def distinct_subseq_brute(s, t, i=None, j=None):
    if i is None: i = len(s)
    if j is None: j = len(t)
    if j == 0:
        return 1  # Empty t is a subsequence of any string
    if i == 0:
        return 0  # Non-empty t cannot be formed from empty s
    result = distinct_subseq_brute(s, t, i - 1, j)  # Skip s[i-1]
    if s[i-1] == t[j-1]:
        result += distinct_subseq_brute(s, t, i - 1, j - 1)  # Use s[i-1]
    return result

# Tabulation: O(m*n) time, O(n) space
def distinct_subseq_tab(s, t):
    m, n = len(s), len(t)
    # dp[j] = number of ways to form t[0..j-1]
    dp = [0] * (n + 1)
    dp[0] = 1  # Empty t: one way (use no characters)

    for i in range(1, m + 1):
        # Traverse right to left to avoid overwriting values we need
        for j in range(min(i, n), 0, -1):
            if s[i-1] == t[j-1]:
                dp[j] += dp[j-1]
    return dp[n]

# Test: distinct_subseq_tab("rabbbit", "rabbit") = 3
# The three ways:
#   ra_bbit -> rabbit
#   rab_bit -> rabbit
#   rabb_it -> rabbit (choosing which 'b' to skip)

# Test: distinct_subseq_tab("babgbag", "bag") = 5

Complexity Summary

ProblemBrute ForceDP TimeOptimized Space
Longest Palindromic Substring O(n^3) O(n^2) O(1) with expand
Word Break O(2^n) O(n^2) O(n)
Regex Matching O(2^(m+n)) O(m × n) O(n)
Interleaving String O(2^(m+n)) O(m × n) O(n)
Distinct Subsequences O(2^m) O(m × n) O(n)

Key Takeaways

  • String DP problems typically have states based on positions in one or two strings.
  • Palindrome problems use interval DP where dp[i][j] represents the substring s[i..j].
  • Word break is a segmentation problem that checks all possible prefix splits.
  • Regex matching requires careful handling of the '*' wildcard, which can match zero or more characters.
  • Distinct subsequences and interleaving string both use the include/skip pattern on characters.