DP on Strings: LCS, Edit Distance, and Pattern Matching

Strings are one of the richest domains for dynamic programming. Two strings, a 2D table, and a recurrence relation — that is the recipe behind some of the most iconic DP problems. From autocorrect engines (edit distance) to DNA sequence alignment (LCS) to regex engines (pattern matching), string DP appears everywhere.

---

1. Longest Common Subsequence (LCS)

Problem: given two strings s and t, find the length of their longest common subsequence. A subsequence does not need to be contiguous.

The Recurrence

Let dp[i][j] = length of LCS of s[0..i-1] and t[0..j-1].

• If s[i-1] == t[j-1]: dp[i][j] = dp[i-1][j-1] + 1 (extend the match)
• Else: dp[i][j] = max(dp[i-1][j], dp[i][j-1]) (skip one character from either string)

Python Implementation

def longest_common_subsequence(s: str, t: str) -> int:
    """
    Compute the length of the longest common subsequence.

    Time: O(m * n)
    Space: O(m * n)
    """
    m, n = len(s), len(t)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s[i - 1] == t[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]


print(longest_common_subsequence("ABCBDAB", "BDCAB"))  # 4 ("BCAB")

Reconstructing the LCS

def lcs_string(s: str, t: str) -> str:
    """Return the actual LCS string, not just its length."""
    m, n = len(s), len(t)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

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

    # Backtrack to find the actual subsequence
    result = []
    i, j = m, n
    while i > 0 and j > 0:
        if s[i - 1] == t[j - 1]:
            result.append(s[i - 1])
            i -= 1
            j -= 1
        elif dp[i - 1][j] > dp[i][j - 1]:
            i -= 1
        else:
            j -= 1

    return "".join(reversed(result))


print(lcs_string("ABCBDAB", "BDCAB"))  # "BCAB"

---

2. Space-Optimized LCS

Since each row of the DP table only depends on the previous row, we can reduce space from O(mn) to O(min(m, n)).

def lcs_optimized(s: str, t: str) -> int:
    """
    LCS with O(min(m,n)) space.
    """
    # Make sure we iterate over the longer string in the outer loop
    if len(s) < len(t):
        s, t = t, s

    m, n = len(s), len(t)
    prev = [0] * (n + 1)
    curr = [0] * (n + 1)

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s[i - 1] == t[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]


print(lcs_optimized("ABCBDAB", "BDCAB"))  # 4

---

3. Longest Common Substring

Unlike subsequence, a substring must be contiguous. The recurrence changes subtly.

def longest_common_substring(s: str, t: str) -> int:
    """
    Find the length of the longest common substring.

    Key difference from LCS: when characters don't match,
    reset to 0 instead of taking the max.

    Time: O(m * n), Space: O(m * n)
    """
    m, n = len(s), len(t)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    max_len = 0

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s[i - 1] == t[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
                max_len = max(max_len, dp[i][j])
            # else: dp[i][j] stays 0 (reset!)

    return max_len


print(longest_common_substring("ABABC", "BABCBA"))  # 4 ("BABC")

Finding the Actual Substring

def longest_common_substring_str(s: str, t: str) -> str:
    """Return the actual longest common substring."""
    m, n = len(s), len(t)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    max_len = 0
    end_idx = 0  # end index in s

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s[i - 1] == t[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
                if dp[i][j] > max_len:
                    max_len = dp[i][j]
                    end_idx = i

    return s[end_idx - max_len : end_idx]


print(longest_common_substring_str("ABABC", "BABCBA"))  # "BABC"

---

4. Edit Distance (Levenshtein Distance)

Problem: given two strings s and t, find the minimum number of operations (insert, delete, replace) to transform s into t.

This is used in spell checkers, DNA alignment, and diff tools.

Recurrence

Let dp[i][j] = edit distance between s[0..i-1] and t[0..j-1].

• If s[i-1] == t[j-1]: dp[i][j] = dp[i-1][j-1] (no operation needed)
• Else: dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])
  • dp[i-1][j-1] + 1: replace s[i-1] with t[j-1]
  • dp[i-1][j] + 1: delete s[i-1]
  • dp[i][j-1] + 1: insert t[j-1]

def edit_distance(s: str, t: str) -> int:
    """
    Compute the minimum edit distance (Levenshtein distance).

    Time: O(m * n), Space: O(m * n)
    """
    m, n = len(s), len(t)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    # Base cases
    for i in range(m + 1):
        dp[i][0] = i  # delete all chars from s
    for j in range(n + 1):
        dp[0][j] = j  # insert all chars of t

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s[i - 1] == t[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
                    dp[i][j - 1],       # insert
                )

    return dp[m][n]


print(edit_distance("kitten", "sitting"))  # 3
print(edit_distance("sunday", "saturday"))  # 3

Space-Optimized Edit Distance

def edit_distance_optimized(s: str, t: str) -> int:
    """Edit distance with O(min(m,n)) space."""
    if len(s) < len(t):
        s, t = t, s

    m, n = len(s), len(t)
    prev = list(range(n + 1))
    curr = [0] * (n + 1)

    for i in range(1, m + 1):
        curr[0] = i
        for j in range(1, n + 1):
            if s[i - 1] == t[j - 1]:
                curr[j] = prev[j - 1]
            else:
                curr[j] = 1 + min(prev[j - 1], prev[j], curr[j - 1])
        prev, curr = curr, [0] * (n + 1)

    return prev[n]


print(edit_distance_optimized("kitten", "sitting"))  # 3

---

5. Longest Palindromic Subsequence

Problem: find the longest subsequence of a string that is a palindrome.

Key insight: the longest palindromic subsequence of s equals the LCS of s and reverse(s).

def longest_palindromic_subsequence(s: str) -> int:
    """
    LPS = LCS(s, reverse(s)).

    Time: O(n^2), Space: O(n^2)
    """
    return longest_common_subsequence(s, s[::-1])


print(longest_palindromic_subsequence("bbbab"))  # 4 ("bbbb")
print(longest_palindromic_subsequence("cbbd"))   # 2 ("bb")

Direct DP (Without LCS Reduction)

def lps_direct(s: str) -> int:
    """
    Direct DP for longest palindromic subsequence.

    dp[i][j] = LPS of s[i..j]
    """
    n = len(s)
    dp = [[0] * n for _ in range(n)]

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

    # Fill for increasing lengths
    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]


print(lps_direct("bbbab"))  # 4

---

6. Wildcard Matching

Problem: given a string s and a pattern p with ? (matches any single character) and * (matches any sequence including empty), determine if the pattern matches the entire string.

def wildcard_match(s: str, p: str) -> bool:
    """
    LeetCode 44: Wildcard Matching.

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

    Time: O(m * n), Space: O(m * n)
    """
    m, n = len(s), len(p)
    dp = [[False] * (n + 1) for _ in range(m + 1)]

    dp[0][0] = True

    # Pattern with leading *s can match empty string
    for j in range(1, n + 1):
        if p[j - 1] == '*':
            dp[0][j] = dp[0][j - 1]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if p[j - 1] == '*':
                # '*' matches zero chars (dp[i][j-1])
                # or one+ chars (dp[i-1][j])
                dp[i][j] = dp[i][j - 1] or dp[i - 1][j]
            elif p[j - 1] == '?' or s[i - 1] == p[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]

    return dp[m][n]


print(wildcard_match("adceb", "*a*b"))    # True
print(wildcard_match("acdcb", "a*c?b"))   # False
print(wildcard_match("", "*"))            # True
print(wildcard_match("abc", "a?c"))       # True

---

7. Regular Expression Matching

Problem: given a string s and a pattern p with . (matches any single character) and * (zero or more of the preceding element), determine if the pattern matches the entire string.

This is harder than wildcard because * modifies the preceding character, not the rest of the pattern.

def regex_match(s: str, p: str) -> bool:
    """
    LeetCode 10: Regular Expression Matching.

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

    Time: O(m * n), Space: O(m * n)
    """
    m, n = len(s), len(p)
    dp = [[False] * (n + 1) for _ in range(m + 1)]

    dp[0][0] = True

    # Patterns like a*, a*b*, a*b*c* 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] == '*':
                # Case 1: zero occurrences of preceding char
                dp[i][j] = dp[i][j - 2]

                # Case 2: one or more occurrences
                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]


print(regex_match("aab", "c*a*b"))    # True (c* = empty, a* = aa, b = b)
print(regex_match("mississippi", "mis*is*p*."))  # False
print(regex_match("ab", ".*"))        # True

---

8. Shortest Common Supersequence

Problem: given two strings s and t, find the shortest string that has both s and t as subsequences.

Key insight: len(SCS) = len(s) + len(t) - len(LCS(s, t)).

def shortest_common_supersequence(s: str, t: str) -> str:
    """
    LeetCode 1092: Shortest Common Supersequence.

    Build the SCS by backtracking through the LCS table.
    """
    m, n = len(s), len(t)

    # Build LCS table
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s[i - 1] == t[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    # Backtrack to build the supersequence
    result = []
    i, j = m, n

    while i > 0 and j > 0:
        if s[i - 1] == t[j - 1]:
            result.append(s[i - 1])
            i -= 1
            j -= 1
        elif dp[i - 1][j] > dp[i][j - 1]:
            result.append(s[i - 1])
            i -= 1
        else:
            result.append(t[j - 1])
            j -= 1

    # Add remaining characters
    while i > 0:
        result.append(s[i - 1])
        i -= 1
    while j > 0:
        result.append(t[j - 1])
        j -= 1

    return "".join(reversed(result))


print(shortest_common_supersequence("abac", "cab"))  # "cabac"

---

9. Distinct Subsequences

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

def num_distinct(s: str, t: str) -> int:
    """
    LeetCode 115: Distinct Subsequences.

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

    Time: O(m * n), Space: O(n)
    """
    m, n = len(s), len(t)
    # Space-optimized: only need previous row
    dp = [0] * (n + 1)
    dp[0] = 1  # empty t can always be formed

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

    return dp[n]


print(num_distinct("rabbbit", "rabbit"))  # 3
print(num_distinct("babgbag", "bag"))     # 5

---

10. Interleaving Strings

Problem: given strings s1, s2, and s3, determine if s3 is formed by interleaving s1 and s2.

def is_interleave(s1: str, s2: str, s3: str) -> bool:
    """
    LeetCode 97: Interleaving String.

    dp[i][j] = True if s3[0..i+j-1] can be formed by
    interleaving s1[0..i-1] and s2[0..j-1]
    """
    m, n = len(s1), len(s2)
    if m + n != len(s3):
        return False

    dp = [False] * (n + 1)
    dp[0] = True

    # Base case: only using s2
    for j in range(1, n + 1):
        dp[j] = dp[j - 1] and s2[j - 1] == s3[j - 1]

    for i in range(1, m + 1):
        dp[0] = dp[0] and s1[i - 1] == s3[i - 1]
        for j in range(1, n + 1):
            dp[j] = (
                (dp[j] and s1[i - 1] == s3[i + j - 1]) or
                (dp[j - 1] and s2[j - 1] == s3[i + j - 1])
            )

    return dp[n]


print(is_interleave("aabcc", "dbbca", "aadbbcbcac"))  # True
print(is_interleave("aabcc", "dbbca", "aadbbbaccc"))   # False

---

11. Summary — When to Use Which

Problem	Time	Space	Key Idea
LCS	O(mn)	O(n) optimized	Match diagonals, skip from sides
Longest Common Substring	O(mn)	O(n) optimized	Reset to 0 on mismatch
Edit Distance	O(mn)	O(n) optimized	Three operations: ins/del/rep
LPS	O(n^2)	O(n^2)	LCS(s, reverse(s))
Wildcard Matching	O(mn)	O(mn)	* matches any sequence
Regex Matching	O(mn)	O(mn)	* modifies preceding char
Shortest Common Superseq	O(mn)	O(mn)	len = m + n - LCS
Distinct Subsequences	O(mn)	O(n)	Count, not find

---

12. Practice Problems

Problem	Platform	Key Technique
Longest Common Subsequence (LC 1143)	LeetCode	LCS
Edit Distance (LC 72)	LeetCode	Levenshtein
Wildcard Matching (LC 44)	LeetCode	Wildcard DP
Regular Expression Matching (LC 10)	LeetCode	Regex DP
Longest Palindromic Subsequence (LC 516)	LeetCode	LPS
Shortest Common Supersequence (LC 1092)	LeetCode	LCS + backtrack
Distinct Subsequences (LC 115)	LeetCode	Counting DP
Interleaving String (LC 97)	LeetCode	2D DP
Minimum ASCII Delete Sum (LC 712)	LeetCode	Weighted LCS variant
Delete Operation for Two Strings (LC 583)	LeetCode	m + n - 2 * LCS

String DP problems are among the most frequently asked in interviews. The 2D table structure is consistent, and once you see the pattern — “what happens when characters match vs don’t match?” — you can derive the recurrence for any new variant.