Dynamic Programming chevron_right String DP Problems: Edit Distance, Palindromes, and Pattern Matching

String DP Problems: Edit Distance, Palindromes, and Pattern Matching

calendar_today schedule 12 min read

Learning Objectives: By the end of this lesson, you will be able to:

  • Master the edit distance problem and understand its applications
  • Solve palindrome-related problems using dynamic programming
  • Implement pattern matching algorithms with DP
  • Optimize string transformations and manipulations
  • Apply string DP techniques to real-world text processing problems

1. Welcome and Introduction (5 minutes)

Icebreaker Activity

Have you ever wondered how your smartphone’s autocorrect feature suggests corrections, or how DNA sequencing algorithms compare genetic sequences? These technologies rely heavily on string dynamic programming! From spell checkers to bioinformatics, from version control systems to natural language processing, string DP algorithms power many of the text processing tools we use daily.

Consider this: when you type “recieve” instead of “receive,” how does the system know what you meant? The answer lies in calculating the minimum number of operations needed to transform one string into another—a classic string DP problem!

Lesson Overview

  • Duration: 90 minutes
  • Prerequisites: 2D DP understanding, string manipulation basics
  • Materials Needed: Python development environment, text examples for testing

2. Learning Objectives and Session Outline (5 minutes)

What We’ll Cover Today:

  1. Edit Distance (Levenshtein Distance) - The foundation of string transformation
  2. Palindrome Problems - Longest palindromic subsequence and substring
  3. Pattern Matching with DP - Wildcard and regex-style matching
  4. String Transformation - Advanced manipulation and optimization
  5. Real-World Applications - From spellcheck to bioinformatics

Success Criteria:

By the end of this session, you should be able to recognize string DP patterns, implement efficient string transformation algorithms, and apply these techniques to solve complex text processing problems.

3. Foundation Knowledge (15-20 minutes)

Core Concepts

Edit Distance Fundamentals

Edit distance measures the minimum number of operations required to transform one string into another. The three basic operations are:

  1. Insert a character
  2. Delete a character
  3. Replace a character

Real-World Analogy: Think of edit distance as the minimum number of keystrokes needed to change one word into another using only insert, delete, and replace operations.

Why This Matters: Edit distance is fundamental to spell checking, DNA sequence alignment, plagiarism detection, and many other applications where we need to measure string similarity.

Palindrome Concepts

A palindrome reads the same forwards and backwards. In DP problems, we often deal with:

  • Longest Palindromic Subsequence: Maximum length subsequence that forms a palindrome
  • Longest Palindromic Substring: Maximum length contiguous substring that is a palindrome
  • Palindrome Partitioning: Minimum cuts to make all parts palindromes

Pattern Matching

Pattern matching with DP allows us to handle complex patterns including:

  • Wildcards: Characters that can match any single character
  • Kleene Stars: Characters that can match zero or more of the preceding character
  • Character Classes: Ranges of valid characters

Key Terminology

  • Edit Distance/Levenshtein Distance: Minimum operations to transform one string to another
  • Subsequence: Characters from original string in same relative order (not necessarily contiguous)
  • Substring: Contiguous portion of a string
  • DP State: Typically represents subproblems on string prefixes

4. Detailed Explanation and Examples (25-30 minutes)

Understanding Edit Distance

The edit distance problem asks: given two strings, what’s the minimum number of operations to transform the first string into the second?

Let’s consider transforming “CAT” into “DOG”:

  • CAT → DAT (replace C with D)
  • DAT → DOT (replace A with O)
  • DOT → DOG (replace T with G) Total: 3 operations

The DP approach builds a table where dp[i][j] represents the minimum operations to transform the first i characters of string1 into the first j characters of string2.

State Transition Logic

For each position (i,j), we have three choices:

  1. Replace: dp[i-1][j-1] + 1 (if characters differ)
  2. Delete: dp[i-1][j] + 1
  3. Insert: dp[i][j-1] + 1

If characters match: dp[i][j] = dp[i-1][j-1]

Practical Applications

Edit distance is used in:

  • Spell checkers: Finding the closest correctly spelled word
  • DNA analysis: Comparing genetic sequences
  • Version control: Computing file differences
  • Plagiarism detection: Measuring text similarity
  • Machine translation: Aligning parallel texts

Common Misconceptions

  1. Misconception: Edit distance only works for similar-length strings Reality: It works for any string lengths and handles insertions/deletions gracefully

  2. Misconception: All operations have equal cost Reality: You can assign different weights to different operations based on your application

5. Live Coding Demonstration (20-25 minutes)

Example 1: Basic Edit Distance

def edit_distance(str1, str2):
    """
    Calculate minimum edit distance between two strings.
    Returns the minimum number of operations needed.
    """
    m, n = len(str1), len(str2)
    
    # Create DP table
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # Initialize base cases
    # Empty string to str2[0:j] requires j insertions
    for j in range(n + 1):
        dp[0][j] = j
    
    # str1[0:i] to empty string requires i deletions
    for i in range(m + 1):
        dp[i][0] = i
    
    # Fill the DP table
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if str1[i-1] == str2[j-1]:
                # Characters match, no operation needed
                dp[i][j] = dp[i-1][j-1]
            else:
                # Take minimum of three operations
                dp[i][j] = 1 + min(
                    dp[i-1][j],    # Delete from str1
                    dp[i][j-1],    # Insert into str1
                    dp[i-1][j-1]   # Replace in str1
                )
    
    return dp[m][n]

# Test the function
print(edit_distance("kitten", "sitting"))  # Output: 3
print(edit_distance("cat", "dog"))         # Output: 3
print(edit_distance("", "abc"))            # Output: 3

Explanation:

  • Line 6-7: Create a 2D table where dp[i][j] represents edit distance between first i chars of str1 and first j chars of str2
  • Line 10-11: Base case - transforming empty string to any string requires insertions
  • Line 14-15: Base case - transforming any string to empty string requires deletions
  • Line 20-21: If characters match, inherit result from diagonal (no operation needed)
  • Line 24-28: If characters don’t match, try all three operations and take minimum

Example 2: Longest Palindromic Subsequence

def longest_palindromic_subsequence(s):
    """
    Find the length of the longest palindromic subsequence.
    A subsequence maintains relative order but need not be contiguous.
    """
    n = len(s)
    
    # dp[i][j] = length of longest palindromic subsequence in s[i:j+1]
    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
    
    # Build for substrings of length 2 to n
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            
            if s[i] == s[j]:
                # Characters match - add 2 to inner subsequence
                if length == 2:
                    dp[i][j] = 2
                else:
                    dp[i][j] = dp[i+1][j-1] + 2
            else:
                # Characters don't match - take max of excluding either end
                dp[i][j] = max(dp[i+1][j], dp[i][j-1])
    
    return dp[0][n-1]

# Test the function
print(longest_palindromic_subsequence("bbbab"))      # Output: 4 ("bbbb")
print(longest_palindromic_subsequence("cbbd"))       # Output: 2 ("bb")
print(longest_palindromic_subsequence("abcdef"))     # Output: 1 (any single char)

Key Points:

  • This problem uses interval DP where we build solutions for increasingly larger substrings
  • When end characters match, we can extend the inner palindrome by 2
  • When they don’t match, we try excluding each end character and take the maximum

Example 3: Wildcard Pattern Matching

def wildcard_match(s, p):
    """
    Match string s against pattern p with wildcards.
    '?' matches any single character
    '*' matches any sequence of characters (including empty)
    """
    m, n = len(s), len(p)
    
    # dp[i][j] = True if s[0:i] matches p[0:j]
    dp = [[False] * (n + 1) for _ in range(m + 1)]
    
    # Empty string matches empty pattern
    dp[0][0] = True
    
    # Handle patterns with leading asterisks
    for j in range(1, n + 1):
        if p[j-1] == '*':
            dp[0][j] = dp[0][j-1]
    
    # Fill the DP table
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if p[j-1] == '*':
                # '*' can match empty string or any character
                dp[i][j] = dp[i][j-1] or dp[i-1][j]
            elif p[j-1] == '?' or s[i-1] == p[j-1]:
                # '?' matches any char, or characters match exactly
                dp[i][j] = dp[i-1][j-1]
            # else: characters don't match, dp[i][j] remains False
    
    return dp[m][n]

# Test the function
print(wildcard_match("aa", "a"))      # False
print(wildcard_match("aa", "*"))      # True
print(wildcard_match("cb", "?a"))     # False
print(wildcard_match("adceb", "*a*b")) # True

Debugging Demonstration

Show common errors and how to fix them:

# Common mistake: Not handling base cases properly
def edit_distance_wrong(str1, str2):
    m, n = len(str1), len(str2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # Missing base case initialization!
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if str1[i-1] == str2[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
    
    return dp[m][n]

# Corrected version includes proper base case initialization
def edit_distance_correct(str1, str2):
    m, n = len(str1), len(str2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # Initialize base cases properly
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j
    
    # Rest of the algorithm...
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if str1[i-1] == str2[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
    
    return dp[m][n]

6. Hands-On Practice (30-40 minutes)

Exercise 1: Basic Edit Distance with Path Reconstruction (15 minutes)

Objective: Implement edit distance and track which operations were performed

Instructions:

  1. Modify the basic edit distance to return both the minimum distance and the sequence of operations
  2. Operations should be represented as tuples: (‘insert’, char), (‘delete’, char), (‘replace’, old_char, new_char)
  3. Test with “cat” → “dog” and verify you get distance 3 with appropriate operations

Starter Code:

def edit_distance_with_path(str1, str2):
    m, n = len(str1), len(str2)
    
    # Your DP table here
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # Track operations for path reconstruction
    operations = [[None] * (n + 1) for _ in range(m + 1)]
    
    # TODO: Initialize base cases and fill table
    # TODO: Reconstruct path from operations table
    
    return dp[m][n], path

# Test your implementation
distance, ops = edit_distance_with_path("cat", "dog")
print(f"Distance: {distance}")
print(f"Operations: {ops}")

Solution:

def edit_distance_with_path(str1, str2):
    m, n = len(str1), len(str2)
    
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    operations = [[None] * (n + 1) for _ in range(m + 1)]
    
    # Initialize base cases
    for i in range(m + 1):
        dp[i][0] = i
        if i > 0:
            operations[i][0] = ('delete', str1[i-1])
    
    for j in range(n + 1):
        dp[0][j] = j
        if j > 0:
            operations[0][j] = ('insert', str2[j-1])
    
    # Fill DP table
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if str1[i-1] == str2[j-1]:
                dp[i][j] = dp[i-1][j-1]
                operations[i][j] = ('match', str1[i-1])
            else:
                delete_cost = dp[i-1][j] + 1
                insert_cost = dp[i][j-1] + 1
                replace_cost = dp[i-1][j-1] + 1
                
                if delete_cost <= insert_cost and delete_cost <= replace_cost:
                    dp[i][j] = delete_cost
                    operations[i][j] = ('delete', str1[i-1])
                elif insert_cost <= replace_cost:
                    dp[i][j] = insert_cost
                    operations[i][j] = ('insert', str2[j-1])
                else:
                    dp[i][j] = replace_cost
                    operations[i][j] = ('replace', str1[i-1], str2[j-1])
    
    # Reconstruct path
    path = []
    i, j = m, n
    while i > 0 or j > 0:
        op = operations[i][j]
        path.append(op)
        
        if op[0] == 'match' or op[0] == 'replace':
            i -= 1
            j -= 1
        elif op[0] == 'delete':
            i -= 1
        else:  # insert
            j -= 1
    
    path.reverse()
    return dp[m][n], path

Exercise 2: Longest Palindromic Substring (15 minutes)

Objective: Find the actual longest palindromic substring, not just its length

Requirements:

  • Return both the length and the actual substring
  • Handle edge cases like empty strings and single characters
  • Optimize for both time and space if possible

Hints:

  • You can solve this with O(n²) time and O(n²) space using DP
  • Alternative: expand around centers for O(n²) time and O(1) space
  • Consider how to track the actual substring coordinates

Exercise 3: Advanced Pattern Matching (10 minutes)

Objective: Implement regex-style matching with ‘.’ and ‘*’

Challenge: Extend the wildcard matching to handle:

  • ‘.’ matches any single character (like ‘?’)
  • ‘*’ means zero or more of the preceding character
  • Pattern “a*” matches “”, “a”, “aa”, “aaa”, etc.
  • Pattern “.*” matches any string

Extension Ideas:

  • Add support for character classes like [abc]
  • Implement the ‘+’ operator (one or more)
  • Add case-insensitive matching

7. Common Pitfalls and Troubleshooting (10 minutes)

Frequent Mistakes

  1. Problem: Base case initialization errors Cause: Forgetting to handle empty string cases or initializing incorrectly Solution: Always consider what happens when one or both strings are empty

  2. Problem: Index confusion in string DP Cause: Mixing up 0-based string indices with 1-based DP table indices Solution: Be consistent with indexing and use clear variable names

  3. Problem: Memory exceeded on large inputs Cause: Using full 2D tables when only previous row/column is needed Solution: Optimize space complexity using rolling arrays

Debugging Tips

  • Print the DP table for small examples to verify correctness
  • Use assert statements to verify base cases
  • Test with edge cases: empty strings, single characters, identical strings
  • For pattern matching, test patterns that start/end with wildcards

8. Best Practices and Professional Tips (5 minutes)

Industry Standards

  • Space Optimization: Use O(min(m,n)) space when possible by keeping only necessary rows/columns
  • Early Termination: For pattern matching, fail fast when impossible matches are detected
  • Input Validation: Always validate inputs and handle edge cases gracefully
  • Unicode Considerations: Be aware of multi-byte characters in real applications

Performance Optimizations

  • Rolling Arrays: Reduce space complexity from O(mn) to O(n)
  • Diagonal Traversal: For some problems, process diagonally to improve cache locality
  • Memoization vs Tabulation: Choose based on whether you need the full table or just the final result

Next Steps in Your Learning Journey

  • Study suffix arrays and suffix trees for advanced string algorithms
  • Learn about approximate string matching and fuzzy search
  • Explore string DP in computational biology (sequence alignment)
  • Practice string problems on coding platforms focusing on optimization

9. Summary and Review (5 minutes)

Key Takeaways

  1. Edit Distance Pattern: Universal framework for string transformation problems
  2. Palindrome DP: Interval-based DP for substring/subsequence problems
  3. Pattern Matching: State-based DP for handling wildcards and complex patterns
  4. Space Optimization: Most string DP can be optimized to use linear space

Quick Review Questions

  1. What’s the time complexity of the basic edit distance algorithm? (O(mn))
  2. How would you modify edit distance to handle weighted operations?
  3. What’s the difference between palindromic substring and subsequence problems?

For Instructors

Teaching Tips

  • Use visual diagrams to show DP table filling process
  • Start with small examples and gradually increase complexity
  • Emphasize the connection between recurrence relations and DP implementation
  • Show how string DP problems often have similar state definitions

Assessment Ideas

  • Give students a new string transformation problem and ask them to identify the DP pattern
  • Quiz on optimizing space complexity for string DP problems
  • Project: implement a simple spell checker using edit distance

Adaptation Notes

  • For beginners: focus more on understanding the recurrence relations before implementation
  • For advanced students: emphasize space optimization and real-world applications
  • Online delivery: use shared coding environments for collaborative debugging