Edit Distance Problem

Given two strings str1 and str2 and the following operations that can be performed on str1. Find the minimum number of edits (operations) required to convert str1 into str2.

All of the following operations have an equal cost of 1:

Insert: Insert a character into str1.
Remove: Remove a character from str1.
Replace: Replace a character in str1 with another.

Examples

Example 1

Input: str1 = "geek", str2 = "gesek"
Output: 1
Explanation: We can insert the character 's' into str1 to make it "gesek".

Example 2

Input: str1 = "cat", str2 = "cut"
Output: 1
Explanation: Replace 'a' with 'u'.

Example 3

Input: str1 = "sunday", str2 = "saturday"
Output: 3
Explanation: Last three characters are same ("day"). We need to convert "sun" to "satur".
1. Replace 'n' with 'r' -> "sur"
2. Insert 'u' -> "suur"
3. Insert 't' -> "sutur"
4. Replace 'u' with 'a' -> "satur" (or equivalent 3 operations: replace 'n' with 'r', replace 'u' with 't', insert 'a'/'u').

Mathematical Substructure

Let m be the length of str1 and n be the length of str2. Let editDist(m, n) be the minimum edits.

If last characters match (str1[m-1] === str2[n-1]): We ignore the last characters and get count for remaining: editDist(m, n) = editDist(m-1, n-1)
If last characters do not match: We consider all three operations and take the minimum: editDist(m, n) = 1 + min(insert, remove, replace)
- Insert: Recur for m and n-1 -> editDist(m, n-1)
- Remove: Recur for m-1 and n -> editDist(m-1, n)
- Replace: Recur for m-1 and n-1 -> editDist(m-1, n-1)

1. Recursive Implementation (Naive)

This naive recursive approach takes O(3^M) time in the worst case.

function editDistRecursive(str1, str2, m, n) {
    // If first string is empty, only option is to insert all characters of second string
    if (m === 0) return n;
 
    // If second string is empty, only option is to remove all characters of first string
    if (n === 0) return m;
 
    // If last characters are same, ignore last char and recur for remaining strings
    if (str1[m - 1] === str2[n - 1]) {
        return editDistRecursive(str1, str2, m - 1, n - 1);
    }
 
    // If last characters are not same, consider all three operations
    return 1 + Math.min(
        editDistRecursive(str1, str2, m, n - 1),    // Insert
        editDistRecursive(str1, str2, m - 1, n),    // Remove
        editDistRecursive(str1, str2, m - 1, n - 1) // Replace
    );
}

2. Memoization Implementation (Top-Down DP)

function editDistMemo(str1, str2) {
    const m = str1.length;
    const n = str2.length;
    const memo = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(-1));
 
    function helper(i, j) {
        if (i === 0) return j;
        if (j === 0) return i;
 
        if (memo[i][j] !== -1) return memo[i][j];
 
        if (str1[i - 1] === str2[j - 1]) {
            memo[i][j] = helper(i - 1, j - 1);
        } else {
            memo[i][j] = 1 + Math.min(
                helper(i, j - 1),    // Insert
                helper(i - 1, j),    // Remove
                helper(i - 1, j - 1) // Replace
            );
        }
        return memo[i][j];
    }
 
    return helper(m, n);
}

3. Tabulation Implementation (Bottom-Up DP)

We construct a 2D table dp of size (m+1) x (n+1).

function editDistTabulation(str1, str2) {
    const m = str1.length;
    const n = str2.length;
    const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
 
    // Fill base cases
    for (let i = 0; i <= m; i++) {
        dp[i][0] = i; // Min operations to convert str1[0..i-1] to empty string (remove all)
    }
    for (let j = 0; j <= n; j++) {
        dp[0][j] = j; // Min operations to convert empty string to str2[0..j-1] (insert all)
    }
 
    // Fill the table in bottom-up manner
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (str1[i - 1] === str2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = 1 + Math.min(
                    dp[i][j - 1],    // Insert
                    dp[i - 1][j],    // Remove
                    dp[i - 1][j - 1] // Replace
                );
            }
        }
    }
 
    return dp[m][n];
}
 
// Driver Code
const str1 = "sunday";
const str2 = "saturday";
console.log("Minimum edits required:", editDistTabulation(str1, str2));
// Output: Minimum edits required: 3

Complexity Analysis

Time Complexity: O(M * N)
- We fill a 2D matrix of size M * N where each cell takes O(1) time.
Space Complexity: O(M * N)
- To store the DP lookup table.

Coin Change Problem Longest Increasing Subsequence