Edit Distance (Levenshtein Distance)

Edit Distance is a classic dynamic programming problem that measures the minimum number of operations required to transform one string into another.

The allowed operations are:

• Inserting a character
• Deleting a character
• Replacing a character

Each operation has a cost of 1.

---

Problem Definition

Given two strings:

• s – the source string
• t – the target string

Determine the minimum number of operations required to transform string s into string t.

Example:

• s = "kitten"
• t = "sitting"

Result: 3 (replacement, replacement, insertion)

For example, `"kitten"` can be transformed into `"sitting"` in three operations: 1. Replace `k` with `s`: `"sitten"`. 2. Replace `e` with `i`: `"sittin"`. 3. Insert `g` at the end: `"sitting"`. Therefore, the edit distance is 3.

Note: Standard Levenshtein distance does not treat swapping two adjacent characters as a single operation. If adjacent transpositions are allowed as one operation, a related variant is the Damerau–Levenshtein distance.

---

Why Dynamic Programming?

When we consider prefixes of the strings, the problem naturally breaks down into smaller subproblems.

Edit Distance has:

• Optimal substructure
• Overlapping subproblems

This makes it an ideal problem for dynamic programming.

---

DP State

We define:

dp[i][j] = the minimum number of operations
required to transform the first i characters of string s
into the first j characters of string t

---

Base Cases

• dp[0][j] = j (insert j characters)
• dp[i][0] = i (delete i characters)

---

Transition (DP Recurrence)

If the last characters are equal:

dp[i][j] = dp[i-1][j-1]

If they are different:

dp[i][j] = 1 + min(
    dp[i-1][j],     // deletion
    dp[i][j-1],     // insertion
    dp[i-1][j-1]    // replacement
)

---

Implementation (C++)

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int min3(int a, int b, int c) {
    return min(a, min(b, c));
}

int main() {
    string source, target;
    cin >> source >> target;

    int n = source.size();
    int m = target.size();

    vector<vector<int>> dp(
        n + 1, vector<int>(m + 1, 0)
    );

    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            if (i == 0) {
                dp[i][j] = j;
            } else if (j == 0) {
                dp[i][j] = i;
            } else if (source[i - 1] == target[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = 1 + min3(
                    dp[i - 1][j],     // deletion
                    dp[i][j - 1],     // insertion
                    dp[i - 1][j - 1]  // replacement
                );
            }
        }
    }

    cout << "Edit distance: " << dp[n][m];

    return 0;
}

Example Input and Output

Input:

kitten sitting

Output:

Edit distance: 3

The minimum edit distance is 3. We can transform kitten into sitting by performing two replacements and one insertion.

---

Time and Space Complexity

• Time complexity: O(n · m)
• Space complexity: O(n · m)

where n and m are the lengths of the strings.

Advanced Note: Space Optimization

The standard implementation stores the entire DP table and therefore requires O(n · m) space. However, each cell depends only on the previous row and the current row. This means we can reduce the space complexity to O(min(n, m)) by maintaining only two rows.

The time complexity remains O(n · m), but the memory usage can be significantly reduced for long strings. This optimization is useful when the edit distance is needed but the complete DP table is not required.

---

Space-Optimized Implementation (Two DP Arrays)

The standard Edit Distance algorithm stores the entire DP table, which requires O(n · m) space. However, each state depends only on the previous row and the already computed values in the current row. Therefore, we can optimize the memory usage by maintaining only two one-dimensional DP arrays.

The previous array stores the results from the previous row, while the current array stores the results for the row currently being calculated. After each row is completed, the two arrays are swapped.

To achieve O(min(n, m)) space complexity, we make the shorter string the second string, so that the DP arrays have only m + 1 elements, where m is the length of the shorter string.

Implementation (C++)

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int min3(int a, int b, int c) {
    return min(a, min(b, c));
}

int main() {
    string source, target;
    cin >> source >> target;

    // Keep target as the shorter string
    if (target.size() > source.size()) {
        swap(source, target);
    }

    int n = static_cast<int>(source.size());
    int m = static_cast<int>(target.size());

    vector<int> previous(m + 1);
    vector<int> current(m + 1);

    // Base case: converting an empty string into a prefix of target
    for (int j = 0; j <= m; j++) {
        previous[j] = j;
    }

    for (int i = 1; i <= n; i++) {
        // Convert a prefix of source into an empty string
        current[0] = i;

        for (int j = 1; j <= m; j++) {
            if (source[i - 1] == target[j - 1]) {
                current[j] = previous[j - 1];
            } else {
                current[j] = 1 + min3(
                    previous[j],      // deletion
                    current[j - 1],   // insertion
                    previous[j - 1]   // replacement
                );
            }
        }

        // The current row becomes the previous row
        swap(previous, current);
    }

    cout << "Edit distance: " << previous[m] << '\n';

    return 0;
}

Example Input and Output

Input:

kitten sitting

Output:

Edit distance: 3

Complexity Analysis

• Time Complexity: O(n · m), because each DP state is calculated once.
• Space Complexity: O(min(n, m)), because only two arrays of length min(n, m) + 1 are stored.

This optimization is useful when working with long strings and when only the final edit distance is required. If the complete DP table is needed to reconstruct the actual sequence of edits, the standard two-dimensional implementation is more convenient.

Practical Applications

Edit Distance is used in:

• Spell checking
• Approximate string matching and fuzzy search
• Bioinformatics (DNA sequences)
• Natural language processing

---

Connections to Other DP Problems

Edit Distance is related to:

• Longest Common Subsequence (LCS)
• Grid DP problems
• String alignment problems

Understanding this problem is an important step toward mastering more advanced dynamic programming techniques.