Edit Distance Problem: Dynamic Programming Deep Dive with Java

Every time you mistype a word and your IDE quietly corrects it, or you run git diff and see which lines changed, or a bioinformatics pipeline aligns two DNA strands — the edit distance algorithm is likely doing the heavy lifting. It's one of those rare algorithms that quietly powers a dozen industries simultaneously. Knowing it deeply, not just being able to recite the recurrence relation, is what separates candidates who get offers from those who don't.

The edit distance problem (formally called Levenshtein distance) asks: given two strings, what is the minimum number of single-character operations — insert, delete, or substitute — required to transform one string into the other? The naive recursive solution recomputes the same subproblems exponentially. Dynamic programming collapses that exponential tree into an O(m×n) table where every cell is computed exactly once. The trick is recognising that the optimal answer for transforming any prefix of string A into any prefix of string B depends only on three smaller subproblems — and that insight is the whole game.

By the end of this article you'll be able to: build the full DP table from scratch and explain every cell intuitively, reconstruct the actual sequence of edit operations (not just the count), optimize the solution down to O(min(m,n)) space, handle Unicode and multi-byte strings correctly, and answer every interview follow-up an interviewer can throw at you. Let's build it piece by piece.

What is Edit Distance (Levenshtein Distance)? — Plain English

Edit Distance (also called Levenshtein Distance) measures how many single-character operations — insertions, deletions, or substitutions — are needed to transform one string into another. For example, transforming 'kitten' into 'sitting' requires 3 operations: substitute k->s, substitute e->i, insert g at the end.

Real-world uses: spell checkers compute edit distance to suggest corrections. DNA sequence alignment measures how genetically similar two organisms are. Git merge tools detect which lines were changed, inserted, or deleted.

But here's the thing: the algorithm doesn't care about semantics — it's purely a counting problem. The cost of each operation is assumed to be 1. That assumption breaks in some production systems where substitution cost differs (e.g., keyboard adjacency weighting). We'll get to that later.

How Edit Distance (Levenshtein Distance) Works — Step by Step

Define dp[i][j] = minimum edit distance between the first i characters of word1 and the first j characters of word2.

Base cases: dp[0][j] = j (transform empty string to word2[0..j-1] requires j insertions). dp[i][0] = i (transform word1[0..i-1] to empty string requires i deletions).

Recurrence: If word1[i-1] == word2[j-1]: dp[i][j] = dp[i-1][j-1] (characters match — no operation needed). Else: dp[i][j] = 1 + min( dp[i-1][j], # delete word1[i-1] dp[i][j-1], # insert word2[j-1] into word1 dp[i-1][j-1] # substitute word1[i-1] with word2[j-1] )

Time: O(mn). Space: O(mn) for full table, O(min(m,n)) with rolling rows.

Worked Example — Tracing the Algorithm

Transform 'horse' into 'ros'.

dp table (rows=horse, cols=ros): '' r o s '' [ 0, 1, 2, 3 ] h [ 1, 1, 2, 3 ] o [ 2, 2, 1, 2 ] r [ 3, 2, 2, 2 ] s [ 4, 3, 3, 2 ] e [ 5, 4, 4, 3 ]

Fill example at dp[2][2] (o vs o): word1[1]='o' == word2[1]='o'. dp[2][2] = dp[1][1] = 1. Fill at dp[5][3] (e vs s): 'e' != 's'. min(dp[4][3], dp[5][2], dp[4][2]) = min(2,4,3) = 2. Add 1 = 3.

Answer: dp[5][3] = 3. Operations: delete h, delete r, substitute e->s. (or: substitute h->r, delete o, delete r... multiple valid paths)

Implementation

The following Java implementation demonstrates Edit Distance (Levenshtein Distance) with clear comments. It uses the full DP table for clarity; the two-row optimization is shown in the next section.

package io.thecodeforge.dp;

public class EditDistance {
    public static int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        int[][] dp = new int[m + 1][n + 1];

        // Base cases
        for (int i = 0; i <= m; i++) dp[i][0] = i;
        for (int j = 0; j <= n; j++) dp[0][j] = j;

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = 1 + Math.min(
                        dp[i - 1][j],    // delete
                        Math.min(
                            dp[i][j - 1],    // insert
                            dp[i - 1][j - 1] // substitute
                        )
                    );
                }
            }
        }
        return dp[m][n];
    }

    public static void main(String[] args) {
        System.out.println(minDistance("horse", "ros"));    // 3
        System.out.println(minDistance("kitten", "sitting")); // 3
        System.out.println(minDistance("", "abc"));          // 3
    }
}

Space Optimization: Two-Row DP

The full DP table uses O(m*n) memory, which can be a problem for large strings (e.g., DNA sequences of length 10^5). Notice that each row dp[i] depends only on dp[i-1] (the previous row). We can store just two rows and swap after each iteration. This reduces space to O(min(m,n)) if we always orient the shorter string as the columns.

Implementation in Java:

```java package io.thecodeforge.dp;

public class EditDistanceOptimized { public static int minDistance(String word1, String word2) { if (word1.length() < word2.length()) { String tmp = word1; word1 = word2; word2 = tmp; } int m = word1.length(), n = word2.length(); int[] prev = new int[n + 1]; int[] curr = new int[n + 1]; for (int j = 0; j <= n; j++) prev[j] = j; for (int i = 1; i <= m; i++) { curr[0] = i; for (int j = 1; j <= n; j++) { if (word1.charAt(i - 1) == word2.charAt(j - 1)) { curr[j] = prev[j - 1]; } else { curr[j] = 1 + Math.min(prev[j], Math.min(curr[j - 1], prev[j - 1])); } } int[] temp = prev; prev = curr; curr = temp; } return prev[n]; } } ```

Time remains O(m*n), space drops to O(n). This is the version you'd use when handling 10K+ character strings in production.

Backtracking to Reconstruct Operations

Knowing the edit distance number is useful, but often you need the actual sequence of operations. For example, when displaying a diff to a user, you want to show which characters were inserted, deleted, or substituted.

To reconstruct operations, you start from dp[m][n] and walk backwards to dp[0][0]. At each step: - If characters match (word1[i-1] == word2[j-1]), move diagonally upward (no operation). - If not, check which adjacent cell gave the minimum: dp[i-1][j-1] + 1 → substitution of word1[i-1] with word2[j-1] dp[i-1][j] + 1 → deletion of word1[i-1] * dp[i][j-1] + 1 → insertion of word2[j-1]

Record operations in reverse order, then reverse them at the end.

This is O(m+n) additional space and time. Production systems that need to show user-friendly diffs (e.g., Git) use a similar backtracking approach but optimise with traceback pointers stored during the forward pass.

Production Considerations and Pitfalls

Edit distance seems simple until you put it in production. Here are the real-world issues:

1. Unicode and multi-byte characters: charAt(i) in Java gives a UTF-16 code unit, not a code point. Comparing code units can break for emoji or characters outside the Basic Multilingual Plane. Use codePointAt and codePointCount.
2. Operation costs aren't always 1: In some applications (e.g., DNA alignment), substitution might cost 2, or insertion/deletion might have different weights. The algorithm generalises easily by replacing '1' with a cost matrix.
3. Large strings: O(m*n) time is fine for 1000 chars, but for 100,000 chars it's 10^10 operations — you need to switch to approximate algorithms like Wu-Manber.
4. Memory fragmentation: Using a full 2D array of ints for long strings can cause OOM. Prefer the two-row optimisation, or use a single row with manual diagonal caching.
5. Negative costs or cycles: If any operation cost is negative, dynamic programming fails (since the problem is no longer optimal substructure with non-negative weights). Use Bellman-Ford or similar for edit distance with negative costs (rare).