✏️ Edit Distance Fundamentals

🎯 What is Edit Distance?

Edit distance (also known as Levenshtein distance) is a way of quantifying how dissimilar two strings are by counting the minimum number of operations required to transform one string into the other.

Operations: Insertion, Deletion, Substitution (Replacement)
Goal: Transform string A → string B with minimum cost
Key Insight: Dynamic programming on prefixes
Applications: Spell checking, DNA sequence alignment, NLP

📌 DP on Strings📌 O(m×n) Time📌 O(min(m,n)) Space

The Core Idea

Key Insight: The edit distance between two strings can be computed by considering the last characters of each string and choosing the optimal operation.

Three Core Operations:

Insert Add a character to transform s1 → s2
Delete Remove a character from s1
Replace Change a character in s1 to match s2

# Edit Distance Problem Statement
# Given two strings s1 and s2
# Find the minimum number of operations to transform s1 → s2

# Operations (each costs 1):
# 1. Insert a character
# 2. Delete a character  
# 3. Replace a character

# Example:
# s1 = "kitten", s2 = "sitting"
# kitten → sitten (replace 'k' with 's')
# sitten → sittin (replace 'e' with 'i')
# sittin → sitting (insert 'g')
# Edit Distance = 3

📝 Levenshtein Distance (Classic)

🎯 The Original Edit Distance

Named after Vladimir Levenshtein (1965), this is the most common edit distance metric. It uses three operations: insertion, deletion, and substitution, each with cost 1.

Insertion: Add a character (cost 1)
Deletion: Remove a character (cost 1)
Substitution: Replace a character (cost 1)
Distance: Minimum number of single-character edits

# Levenshtein Distance
def levenshtein(s1, s2):
    m, n = len(s1), len(s2)
    
    # dp[i][j] = distance between first i chars of s1 and first j chars of s2
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # Base cases: delete all characters from s1 or insert all from s2
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1]  # No operation needed
            else:
                dp[i][j] = 1 + min(
                    dp[i-1][j],    # Delete from s1
                    dp[i][j-1],    # Insert into s1
                    dp[i-1][j-1]   # Replace
                )
    
    return dp[m][n]

# Example:
# levenshtein("kitten", "sitting") → 3
# levenshtein("saturday", "sunday") → 3

🔧 Operations: Insert, Delete, Replace

🎯 Understanding the Three Operations

Insert (cost = 1): Add a character to s1 to match s2
Example: s1="cat", s2="cart" → insert 'r' → "cart"
Delete (cost = 1): Remove a character from s1
Example: s1="cart", s2="cat" → delete 'r' → "cat"
Replace (cost = 1): Change a character in s1
Example: s1="cat", s2="bat" → replace 'c' with 'b' → "bat"

# Visualizing the Operations
# Transforming "kitten" → "sitting"

# Step 1: Replace 'k' with 's'
# kitten → sitten

# Step 2: Replace 'e' with 'i'
# sitten → sittin

# Step 3: Insert 'g'
# sittin → sitting

# Total cost = 3

# Alternative path:
# kitten → kitten (delete 'k') → itten
# itten → sitten (insert 's') → sitten
# sitten → sittin (replace 'e' with 'i')
# sittin → sitting (insert 'g')
# Total cost = 4 (not optimal)

🧮 DP Formulation & Recurrence

🎯 The DP Recurrence

Let dp[i][j] be the edit distance between s1[0..i-1] and s2[0..j-1].

Base Cases:
- dp[i][0] = i (delete i characters)
- dp[0][j] = j (insert j characters)
Recurrence:
- If s1[i-1] == s2[j-1]: dp[i][j] = dp[i-1][j-1]
- Else: dp[i][j] = 1 + min(
    dp[i-1][j], // Delete
    dp[i][j-1], // Insert
    dp[i-1][j-1] // Replace )

# DP Table for "kitten" → "sitting"
#        ''  s  i  t  t  i  n  g
# ''     0   1  2  3  4  5  6  7
# k      1   1  2  3  4  5  6  7
# i      2   2  1  2  3  4  5  6
# t      3   3  2  1  2  3  4  5
# t      4   4  3  2  1  2  3  4
# e      5   5  4  3  2  2  3  4
# n      6   6  5  4  3  3  2  3

# Answer: dp[6][7] = 3

# Key observation: dp[i][j] only depends on:
# - dp[i-1][j-1] (diagonal)
# - dp[i-1][j]   (up)
# - dp[i][j-1]   (left)
# This allows space optimization!

💻 Implementation & Optimization

🎯 Space-Optimized Implementation

The DP table can be reduced from O(m×n) to O(min(m,n)) space by storing only two rows at a time.

# Space-Optimized Edit Distance (O(min(m,n)) space)
def edit_distance_optimized(s1, s2):
    m, n = len(s1), len(s2)
    
    # Ensure s1 is the shorter string for space optimization
    if m > n:
        s1, s2 = s2, s1
        m, n = n, m
    
    # dp[j] represents dp[current_row][j]
    dp = list(range(n + 1))
    
    for i in range(1, m + 1):
        prev = dp[0]  # dp[i-1][0]
        dp[0] = i     # dp[i][0]
        
        for j in range(1, n + 1):
            temp = dp[j]  # dp[i-1][j]
            if s1[i-1] == s2[j-1]:
                dp[j] = prev
            else:
                dp[j] = 1 + min(prev, dp[j-1], dp[j])
            prev = temp
    
    return dp[n]

# Alternative: Use only two rows
def edit_distance_two_rows(s1, s2):
    m, n = len(s1), len(s2)
    prev = list(range(n + 1))
    
    for i in range(1, m + 1):
        curr = [0] * (n + 1)
        curr[0] = i
        for j in range(1, n + 1):
            if s1[i-1] == s2[j-1]:
                curr[j] = prev[j-1]
            else:
                curr[j] = 1 + min(prev[j], curr[j-1], prev[j-1])
        prev = curr
    
    return prev[n]

🔍 Reconstructing the Edits

🎯 Getting the Sequence of Operations

Sometimes we need to know exactly which edits were made, not just the distance. This requires backtracking through the DP table.

# Edit Distance with Reconstruction
def edit_distance_with_edits(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i-1] == s2[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])
    
    # Backtracking
    edits = []
    i, j = m, n
    while i > 0 or j > 0:
        if i > 0 and j > 0 and s1[i-1] == s2[j-1]:
            edits.append(("match", s1[i-1], i-1, j-1))
            i -= 1
            j -= 1
        elif i > 0 and j > 0 and dp[i][j] == dp[i-1][j-1] + 1:
            edits.append(("replace", s1[i-1], s2[j-1], i-1, j-1))
            i -= 1
            j -= 1
        elif i > 0 and dp[i][j] == dp[i-1][j] + 1:
            edits.append(("delete", s1[i-1], i-1))
            i -= 1
        else:  # Insert
            edits.append(("insert", s2[j-1], j-1))
            j -= 1
    
    return dp[m][n], list(reversed(edits))

# Example output for "kitten" → "sitting":
# [
#   ('replace', 'k', 's'),
#   ('replace', 'e', 'i'),
#   ('insert', 'g')
# ]

⚖️ Weighted Edit Distance

🎯 Assigning Different Costs

In many real-world applications, operations have different costs. For example, in DNA sequence alignment, substitutions may have different costs based on the type of mutation.

Insert Cost: Cost of inserting a character
Delete Cost: Cost of deleting a character
Replace Cost: Cost of replacing one character with another
Custom Costs: Different costs for different character pairs

# Weighted Edit Distance
def weighted_edit_distance(s1, s2, insert_cost=1, delete_cost=1, replace_cost=1):
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    for i in range(m + 1):
        dp[i][0] = i * delete_cost
    for j in range(n + 1):
        dp[0][j] = j * insert_cost
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = min(
                    dp[i-1][j] + delete_cost,
                    dp[i][j-1] + insert_cost,
                    dp[i-1][j-1] + replace_cost
                )
    
    return dp[m][n]

# Example with different costs:
# insert_cost=2, delete_cost=2, replace_cost=1
# "kitten" → "sitting": 3 replacements → cost 3
# This encourages substitutions over insert/delete

🔄 Damerau-Levenshtein Distance

🎯 Including Transpositions

Damerau-Levenshtein distance extends Levenshtein distance by including transpositions (swapping adjacent characters) as a single operation. This is more appropriate for human typing errors.

Operations: Insert, Delete, Replace, Transpose (swap adjacent)
Transposition Cost: Usually 1 (same as other operations)
Use Case: Spell checking, OCR correction

# Damerau-Levenshtein Distance
def damerau_levenshtein(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j
    
    last_pos = {}
    for i in range(1, m + 1):
        last_j = 0
        for j in range(1, n + 1):
            cost = 0 if s1[i-1] == s2[j-1] else 1
            
            if s1[i-1] == s2[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])
            
            # Transposition check
            if i > 1 and j > 1 and s1[i-1] == s2[j-2] and s1[i-2] == s2[j-1]:
                dp[i][j] = min(dp[i][j], dp[i-2][j-2] + 1)
    
    return dp[m][n]

# Example:
# damerau_levenshtein("ca", "ac") → 1 (transposition)
# levenshtein("ca", "ac") → 2 (delete + insert or replace + replace)

📊 Hamming Distance

🎯 Distance for Equal-Length Strings

Hamming distance counts the number of positions where two strings of equal length differ. It only allows substitution (no insert/delete).

Constraint: Strings must be the same length
Operation: Only substitution (cost 1 per mismatch)
Time: O(n) | Space: O(1)
Use Case: Error detection, DNA mutation counting

# Hamming Distance
def hamming_distance(s1, s2):
    if len(s1) != len(s2):
        raise ValueError("Strings must have equal length")
    
    return sum(c1 != c2 for c1, c2 in zip(s1, s2))

# Example:
# hamming_distance("karolin", "kathrin") → 4
# hamming_distance("1111", "1001") → 2

# Comparison with Levenshtein:
# s1 = "kitten", s2 = "sitting"
# Hamming: Not applicable (different lengths)
# Levenshtein: 3

🔗 Connection to LCS

🎯 Edit Distance and Longest Common Subsequence

When only insertions and deletions are allowed (no substitutions), the edit distance becomes: m + n - 2 × LCS(m, n)

m + n: Total characters in both strings
LCS: Characters that are already common
Formula: edit_distance = m + n - 2 * LCS

# Edit Distance with only Insert/Delete (No Replace)
def edit_distance_ins_del(s1, s2):
    # This is equivalent to m + n - 2 * LCS(s1, s2)
    m, n = len(s1), len(s2)
    lcs_len = longest_common_subsequence(s1, s2)
    return m + n - 2 * lcs_len

# Levenshtein distance is similar but allows replacements
# (which are more efficient than delete + insert)

# Example:
# s1 = "abc", s2 = "def"
# LCS = 0
# Ins/Del distance = 3 + 3 - 0 = 6
# Levenshtein = 3 (replace 'a'→'d', 'b'→'e', 'c'→'f')

# This shows why substitutions are useful!

🌀 Edit Distance Variations

Longest Common Subsequence (LCS): Only insertions/deletions
Shortest Common Supersequence (SCS): Minimum length string containing both
Levenshtein with custom costs: Weighted operations
Damerau-Levenshtein: With transpositions
Jaro-Winkler Distance: Emphasis on prefix matches
Cosine Distance: Vector-based string similarity
Soundex: Phonetic similarity for names

⏱️ Time & Space Complexities

Variant	Time Complexity	Space Complexity	Notes
Levenshtein	O(m × n)	O(m × n) or O(min(m,n))	Standard DP
Weighted Levenshtein	O(m × n)	O(min(m,n))	Custom costs
Damerau-Levenshtein	O(m × n)	O(m × n)	With transpositions
Hamming Distance	O(n)	O(1)	Equal length only
LCS-based	O(m × n)	O(min(m,n))	No replacements

🌍 Real-World Applications

Spell Checking: Suggest corrections for misspelled words
Bioinformatics: DNA sequence alignment (Smith-Waterman, Needleman-Wunsch)
Natural Language Processing: Text similarity, plagiarism detection
Speech Recognition: Correct transcription errors
OCR Correction: Fix optical character recognition errors
DNA Sequencing: Comparing genetic sequences
Autocorrect: Keyboard auto-correction
Information Retrieval: Fuzzy string matching in search

📝 Interview Patterns & Problems

🎯 Key Interview Questions

Classic Edit Distance: "Find the minimum edit distance between two strings"
One Edit Distance: "Are two strings exactly one edit away?"
Delete Operations: "Make two strings equal by deleting characters"
Minimum ASCII Delete Sum: "Minimize cost of deletions"
Wildcard Matching: "Match strings with * and ? patterns"
Regular Expression: "Implement regex matching with . and *"
Minimum Distance with K: "Distance with at most K edits"

# Common Interview Question Template:
def edit_distance_template(s1, s2):
    m, n = len(s1), len(s2)
    dp = [0] * (n + 1)
    
    # Initialize first row
    for j in range(n + 1):
        dp[j] = j
    
    for i in range(1, m + 1):
        prev = dp[0]  # dp[i-1][0]
        dp[0] = i     # dp[i][0]
        for j in range(1, n + 1):
            temp = dp[j]  # dp[i-1][j]
            if s1[i-1] == s2[j-1]:
                dp[j] = prev
            else:
                dp[j] = 1 + min(prev, dp[j-1], dp[j])
            prev = temp
    
    return dp[n]

# Key optimizations to discuss in interviews:
# 1. Space optimization (two rows or one row)
# 2. Early termination if distance > threshold
# 3. Handling Unicode and multi-byte characters
# 4. Using int arrays instead of Python lists for speed