DSA-135 · FOCUSED PRACTICE

Edit Distance

Advanced · Java 21 · Version 1 · editorial draft

Java reference and baseline verified on JDK 21: 3994 deterministic checks. Learner drafts are not executed.

Understand the problem

Return the minimum number of unit-cost single-code-unit insertions, deletions, and substitutions needed to transform string a into string b. Matching equal code units costs zero. Transposition is not a single allowed operation.

a and b must be non-null Java Strings of at most 2000 UTF-16 code units each. Null throws NullPointerException and excessive length throws IllegalArgumentException. Validate both before selecting a shorter column axis.
All char values are allowed and compared exactly, case-sensitively, without normalization. Operations act on UTF-16 code units, not code points or grapheme clusters. Removing an isolated supplementary symbol represented by a surrogate pair costs two deletions under this contract.
Return only an int minimum cost, with no edit script or tie preference. Empty to length n costs n; equal strings cost zero. Input strings are immutable. Unit insertion/deletion costs are equal, so distance is symmetric and swapping local row/column references preserves the numeric answer. The recursive baseline is for short inputs.

Examples

Input: a="horse", b="ros"
Output: 3
For example horse→rorse by substitution, rorse→rose by deleting the second r, then rose→ros by deleting e.
Input: a="a", b="b"
Output: 1
One substitution is cheaper than delete plus insert.
Input: a="ab", b="ba"
Output: 2
A swap is not one Levenshtein operation; two substitutions suffice.
Input: a="", b="abc"
Output: 3
Insert the three code units.

Before you start

Two-prefix dynamic programming and row compression
Insertion, deletion, substitution, and exact match costs

Recognize the structure

Each edit aligns a source prefix and a target prefix. A cheapest full transformation ends with a match/substitution consuming both final units, a deletion consuming one source unit, or an insertion consuming one target unit. Repeated prefix pairs create a grid of subproblems. The score grid resembles LCS, but the objective, boundaries, mismatch choices, and arithmetic are different.

Your Java attempt

Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.

Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.

Approach, code, and test notes (20,000 characters maximum)

No unsaved text changes · 123/20,000 characters

Self-review

I can define both prefix axes and derive all three paid edit transitions.I can initialize the nonzero boundaries and preserve old diagonal/up values.I can distinguish Levenshtein from transposition and insertion/deletion-only distance, including swapped orientation.

Use the checklist to test your explanation. Checks apply to this visit.

Try before revealing

Hint 1

Describe an optimum transforming two prefixes and calculate the empty-side costs.

Hint 2

What does the last alignment column consume for insert, delete, or substitute?

Hint 3

Save old dp[j] and old diagonal; current dp[j−1] is left. A matching pair costs zero.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Enumerate edit choices on suffix pairs

At suffix positions i,j, an exhausted source needs the remaining target length in insertions, and an exhausted target needs the remaining source length in deletions. Equal next units can be matched at zero cost and advance both. Otherwise try substitute (advance both), delete (advance source), and insert (advance target), add one, and minimize. Without caching, suffix pairs repeat exponentially. A conservative bound is O(3^(m+n)) time and O(m+n+1) live stack depth. Verification limits this method to short strings and compares the reference with an independent shortest-path search over alignment-grid vertices.

Improve the baseline

Name the prefix transformation state

E(i,j) is the minimum cost to transform rows[0..i) into columns[0..j). E(0,j)=j inserts the target prefix, and E(i,0)=i deletes the source prefix. These nonzero boundaries distinguish edit distance from LCS. An index denotes a prefix length, not a position in a changing mutable text.

Derive all final alignment choices

If final code units match, a zero-cost diagonal pair gives E(i−1,j−1). Otherwise substitute from diagonal, delete from up E(i−1,j), or insert from left E(i,j−1), and add one to the minimum. These source/target operation names refer to the displayed row→column orientation. They must not be mixed merely because the numeric recurrence is symmetric.

Understand why equal units can match for free

With nonnegative unit edit costs, there is an optimal alignment pairing equal final units. It never helps to pay for editing an equal pair instead of retaining it; any competing alignment can be adjusted without increasing total cost. This justifies the zero-cost match branch rather than blindly adding one to every diagonal.

Compress the grid while preserving old boundaries

Choose the shorter input as columns, initialize dp[j]=j, and start each new row by saving diagonal=old dp[0], then setting dp[0]=i. Before updating cell j, save up=old dp[j]. New dp[j−1] is left, and diagonal is old dp[j−1]. After writing the minimum, carry diagonal=up for the next column.

Keep orientation and requested output separate

For a shorter original a and longer b, the implementation may display b as source rows and a as target columns. Symmetry preserves the count because insertion and deletion have equal unit cost. A future edit script must translate that reversed orientation back to a→b. The value-only row does not retain choices, and no specific script is promised.

Why it is correct

Boundary transformations

With an empty source, every target unit must be inserted, costing j. With an empty target, every source unit must be deleted, costing i. Those constructions attain the lower bounds because each operation changes length by at most one.

Optimal alignment recurrence

An optimal unit-cost edit transformation has a monotone alignment of the two prefixes. Its final column consumes source only, target only, or both. Removing that column leaves a smaller optimal subproblem; otherwise a cheaper prefix alignment would improve the whole. Every transition also constructs a valid alignment, so minimizing is sound and complete. Equal final units admit the zero-cost diagonal pairing.

Rolling evaluation and exact arithmetic

The initialized row and updated first column provide all boundary values. Saved up and diagonal protect previous-row dependencies until consumed, while left is already final in the current row. Increasing indices therefore compute the full conceptual grid exactly. The answer is at most max(m,n) by substituting the common length and inserting/deleting the remainder, so int is sufficient under the enforced bound.

Complete Java reference and baseline

Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.

import java.util.Objects;

public final class Solution {
    private Solution() {}
    private static void validate(String a, String b) {
        Objects.requireNonNull(a, "a"); Objects.requireNonNull(b, "b");
        if (a.length() > 2_000 || b.length() > 2_000) throw new IllegalArgumentException("text too long");
    }
    public static int minDistance(String a, String b) {
        validate(a, b);
        String rows = a, columns = b;
        if (columns.length() > rows.length()) { rows = b; columns = a; }
        int[] dp = new int[columns.length() + 1];
        for (int j = 0; j <= columns.length(); j++) dp[j] = j;
        for (int i = 1; i <= rows.length(); i++) {
            int diagonal = dp[0];
            dp[0] = i;
            for (int j = 1; j <= columns.length(); j++) {
                int up = dp[j];
                if (rows.charAt(i - 1) == columns.charAt(j - 1)) dp[j] = diagonal;
                else dp[j] = 1 + Math.min(diagonal, Math.min(up, dp[j - 1]));
                diagonal = up;
            }
        }
        return dp[columns.length()];
    }
    // Baseline: enumerate unit-cost edit alternatives without memoization.
    public static int baseline(String a, String b) {
        validate(a, b);
        return suffix(a, b, 0, 0);
    }
    private static int suffix(String a, String b, int i, int j) {
        if (i == a.length()) return b.length() - j;
        if (j == b.length()) return a.length() - i;
        if (a.charAt(i) == b.charAt(j)) return suffix(a, b, i + 1, j + 1);
        return 1 + Math.min(suffix(a, b, i + 1, j + 1), Math.min(suffix(a, b, i + 1, j), suffix(a, b, i, j + 1)));
    }
}

Read the meaningful blocks

Validate and use the shorter column axis

Swapping local references reduces row storage without changing the symmetric value. This relies on equal insertion/deletion costs; a weighted directed variant cannot inherit this swap without rechecking its semantics.

Initialize and advance nonzero boundaries

dp[j]=j records insertion cost before processing a source row. Saving dp[0] before overwriting it with i is essential: the first diagonal of row i is i−1, not i and not zero.

Compare three old/new dependencies

Save old up, use the old diagonal and current left, then update diagonal to the saved up. On a mismatch, add exactly one after choosing the least predecessor cost. The equal-code-unit branch copies diagonal without an edit.

Complexity

For m,n code units, the reference takes O(mn+m+n+1) time and O(min(m,n)+1) auxiliary int storage. The linear terms cover initialization and empty-column row iterations. The output is one int and no edit script is allocated.

The uncached baseline has O(3^(m+n)) upper-bound time and O(m+n+1) stack space, so it is deliberately limited in tests. A full grid costs O(mn) storage and supports ordinary traceback. Changing the text unit or returning a script adds preprocessing/output costs that are excluded from the current value-only API.

Exact-state walkthroughs

Reveal normal and boundary traces

Substitution competes with delete and insert

Input: {"a":"ab","b":"ac"} · Unit-cost edit distance: 1

Step 1 of 13: Choose the shorter column axis and initialize empty-prefix boundaries.

The displayed table includes the initialized first row/column: E(0,j)=j and E(i,0)=i. Interior nulls are uncomputed.

Edit distance — unit-cost alignment and nonzero boundaries

Phase: initial.

Original inputs: {"a":"ab","b":"ac"}. The shorter string is already in columns. Operation labels below transform displayed rows → columns; unit-cost symmetry preserves the original distance.

Rows: "ab". Columns: "ac". Indices are prefix lengths measured in UTF-16 code units.

Conceptual edit cost grid — ∅ is an empty prefix; · is uncomputed
Row / column	0 — ∅	1: "a"	2: "c"
0 — ∅	0	1	2
1: "a"	1	·	·
2: "b"	2	·	·

Actual one-row Java buffer

dp[0]=0 — boundary/final row
dp[1]=1 — boundary/final row
dp[2]=2 — boundary/final row

Boundary row/column values count insertions/deletions. Transposition is not one operation. The complete grid is explanatory history. Java allocates only the shorter score row and constant temporary values; reconstruction requires additional history.

State after this step
Variable	Value
input	`{"a":"ab","b":"ac"}`
phase	`"initial"`
rows	`"ab"`
columns	`"ac"`
swapped	`false`
table	`[[0,1,2],[1,null,null],[2,null,null]]`
dp	`[0,1,2]`

See the affected Java block

 1 import java.util.Objects;
 2 
 3 public final class Solution {
 4     private Solution() {}
 5     private static void validate(String a, String b) {
 6         Objects.requireNonNull(a, "a"); Objects.requireNonNull(b, "b");
 7         if (a.length() > 2_000 || b.length() > 2_000) throw new IllegalArgumentException("text too long");
 8     }
 9     public static int minDistance(String a, String b) {
10         validate(a, b);
11         String rows = a, columns = b;
12         if (columns.length() > rows.length()) { rows = b; columns = a; }
13         int[] dp = new int[columns.length() + 1];
14         for (int j = 0; j <= columns.length(); j++) dp[j] = j;
15         for (int i = 1; i <= rows.length(); i++) {
16             int diagonal = dp[0];
17             dp[0] = i;
18             for (int j = 1; j <= columns.length(); j++) {
19                 int up = dp[j];
20                 if (rows.charAt(i - 1) == columns.charAt(j - 1)) dp[j] = diagonal;
21                 else dp[j] = 1 + Math.min(diagonal, Math.min(up, dp[j - 1]));
22                 diagonal = up;
23             }
24         }
25         return dp[columns.length()];
26     }
27     // Baseline: enumerate unit-cost edit alternatives without memoization.
28     public static int baseline(String a, String b) {
29         validate(a, b);
30         return suffix(a, b, 0, 0);
31     }
32     private static int suffix(String a, String b, int i, int j) {
33         if (i == a.length()) return b.length() - j;
34         if (j == b.length()) return a.length() - i;
35         if (a.charAt(i) == b.charAt(j)) return suffix(a, b, i + 1, j + 1);
36         return 1 + Math.min(suffix(a, b, i + 1, j + 1), Math.min(suffix(a, b, i + 1, j), suffix(a, b, i, j + 1)));
37     }
38 }
39

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Choose the shorter column axis and initialize empty-prefix boundaries.
The displayed table includes the initialized first row/column: E(0,j)=j and E(i,0)=i. Interior nulls are uncomputed.
input
{"a":"ab","b":"ac"}
phase
"initial"
rows
"ab"
columns
"ac"
swapped
false
table
[[0,1,2],[1,null,null],[2,null,null]]
dp
[0,1,2]
Prepare the first column and the old diagonal for this row.
The left-to-right update mixes previous-row entries on the right with current-row entries on the left. The saved diagonal must survive until consumed.
input
{"a":"ab","b":"ac"}
phase
"row-start"
rows
"ab"
columns
"ac"
swapped
false
table
[[0,1,2],[1,null,null],[2,null,null]]
dp
[1,1,2]
i
1
j
0
diagonal
0
Read old up and diagonal together with the current left.
Match consumes both units for zero; mismatch compares substitution=oldDiagonal+1, deletion=up+1, and insertion=left+1 in displayed rows→columns orientation.
input
{"a":"ab","b":"ac"}
phase
"candidate"
rows
"ab"
columns
"ac"
swapped
false
table
[[0,1,2],[1,null,null],[2,null,null]]
dp
[1,1,2]
i
1
j
1
diagonal
0
oldDiagonal
0
up
1
left
1
equal
true
next
0
Write the cell and carry the saved old up as the next diagonal.
oldDiagonal retains the dependency used in this update; live diagonal now carries the old up for the next column. The new dp[j] must not become that next diagonal.
input
{"a":"ab","b":"ac"}
phase
"commit"
rows
"ab"
columns
"ac"
swapped
false
table
[[0,1,2],[1,0,null],[2,null,null]]
dp
[1,0,2]
i
1
j
1
diagonal
1
oldDiagonal
0
up
1
left
1
equal
true
next
0
Read old up and diagonal together with the current left.
Match consumes both units for zero; mismatch compares substitution=oldDiagonal+1, deletion=up+1, and insertion=left+1 in displayed rows→columns orientation.
input
{"a":"ab","b":"ac"}
phase
"candidate"
rows
"ab"
columns
"ac"
swapped
false
table
[[0,1,2],[1,0,null],[2,null,null]]
dp
[1,0,2]
i
1
j
2
diagonal
1
oldDiagonal
1
up
2
left
0
equal
false
next
1
Write the cell and carry the saved old up as the next diagonal.
oldDiagonal retains the dependency used in this update; live diagonal now carries the old up for the next column. The new dp[j] must not become that next diagonal.
input
{"a":"ab","b":"ac"}
phase
"commit"
rows
"ab"
columns
"ac"
swapped
false
table
[[0,1,2],[1,0,1],[2,null,null]]
dp
[1,0,1]
i
1
j
2
diagonal
2
oldDiagonal
1
up
2
left
0
equal
false
next
1
Prepare the first column and the old diagonal for this row.
The left-to-right update mixes previous-row entries on the right with current-row entries on the left. The saved diagonal must survive until consumed.
input
{"a":"ab","b":"ac"}
phase
"row-start"
rows
"ab"
columns
"ac"
swapped
false
table
[[0,1,2],[1,0,1],[2,null,null]]
dp
[2,0,1]
i
2
j
0
diagonal
1
Read old up and diagonal together with the current left.
Match consumes both units for zero; mismatch compares substitution=oldDiagonal+1, deletion=up+1, and insertion=left+1 in displayed rows→columns orientation.
input
{"a":"ab","b":"ac"}
phase
"candidate"
rows
"ab"
columns
"ac"
swapped
false
table
[[0,1,2],[1,0,1],[2,null,null]]
dp
[2,0,1]
i
2
j
1
diagonal
1
oldDiagonal
1
up
0
left
2
equal
false
next
1
Write the cell and carry the saved old up as the next diagonal.
oldDiagonal retains the dependency used in this update; live diagonal now carries the old up for the next column. The new dp[j] must not become that next diagonal.
input
{"a":"ab","b":"ac"}
phase
"commit"
rows
"ab"
columns
"ac"
swapped
false
table
[[0,1,2],[1,0,1],[2,1,null]]
dp
[2,1,1]
i
2
j
1
diagonal
0
oldDiagonal
1
up
0
left
2
equal
false
next
1
Read old up and diagonal together with the current left.
Match consumes both units for zero; mismatch compares substitution=oldDiagonal+1, deletion=up+1, and insertion=left+1 in displayed rows→columns orientation.
input
{"a":"ab","b":"ac"}
phase
"candidate"
rows
"ab"
columns
"ac"
swapped
false
table
[[0,1,2],[1,0,1],[2,1,null]]
dp
[2,1,1]
i
2
j
2
diagonal
0
oldDiagonal
0
up
1
left
1
equal
false
next
1
Write the cell and carry the saved old up as the next diagonal.
oldDiagonal retains the dependency used in this update; live diagonal now carries the old up for the next column. The new dp[j] must not become that next diagonal.
input
{"a":"ab","b":"ac"}
phase
"commit"
rows
"ab"
columns
"ac"
swapped
false
table
[[0,1,2],[1,0,1],[2,1,1]]
dp
[2,1,1]
i
2
j
2
diagonal
1
oldDiagonal
0
up
1
left
1
equal
false
next
1
Return the full-prefix score from the final row.
Unit insertion/deletion costs make the score symmetric even when axes are swapped. A returned edit script would need direction mapping and additional history.
input
{"a":"ab","b":"ac"}
phase
"complete"
rows
"ab"
columns
"ac"
swapped
false
table
[[0,1,2],[1,0,1],[2,1,1]]
dp
[2,1,1]
Return the documented result.
Displayed grids, snapshots and saved candidate annotations are teaching history, excluded from the Java implementation workspace. BigInteger counts use exact decimal strings in trace data.
result
1

Transposition is not a single edit

Input: {"a":"ab","b":"ba"} · Unit-cost edit distance: 2

Step 1 of 13: Choose the shorter column axis and initialize empty-prefix boundaries.

The displayed table includes the initialized first row/column: E(0,j)=j and E(i,0)=i. Interior nulls are uncomputed.

Edit distance — unit-cost alignment and nonzero boundaries

Phase: initial.

Original inputs: {"a":"ab","b":"ba"}. The shorter string is already in columns. Operation labels below transform displayed rows → columns; unit-cost symmetry preserves the original distance.

Rows: "ab". Columns: "ba". Indices are prefix lengths measured in UTF-16 code units.

Conceptual edit cost grid — ∅ is an empty prefix; · is uncomputed
Row / column	0 — ∅	1: "b"	2: "a"
0 — ∅	0	1	2
1: "a"	1	·	·
2: "b"	2	·	·

Actual one-row Java buffer

dp[0]=0 — boundary/final row
dp[1]=1 — boundary/final row
dp[2]=2 — boundary/final row

State after this step
Variable	Value
input	`{"a":"ab","b":"ba"}`
phase	`"initial"`
rows	`"ab"`
columns	`"ba"`
swapped	`false`
table	`[[0,1,2],[1,null,null],[2,null,null]]`
dp	`[0,1,2]`

See the affected Java block

 1 import java.util.Objects;
 2 
 3 public final class Solution {
 4     private Solution() {}
 5     private static void validate(String a, String b) {
 6         Objects.requireNonNull(a, "a"); Objects.requireNonNull(b, "b");
 7         if (a.length() > 2_000 || b.length() > 2_000) throw new IllegalArgumentException("text too long");
 8     }
 9     public static int minDistance(String a, String b) {
10         validate(a, b);
11         String rows = a, columns = b;
12         if (columns.length() > rows.length()) { rows = b; columns = a; }
13         int[] dp = new int[columns.length() + 1];
14         for (int j = 0; j <= columns.length(); j++) dp[j] = j;
15         for (int i = 1; i <= rows.length(); i++) {
16             int diagonal = dp[0];
17             dp[0] = i;
18             for (int j = 1; j <= columns.length(); j++) {
19                 int up = dp[j];
20                 if (rows.charAt(i - 1) == columns.charAt(j - 1)) dp[j] = diagonal;
21                 else dp[j] = 1 + Math.min(diagonal, Math.min(up, dp[j - 1]));
22                 diagonal = up;
23             }
24         }
25         return dp[columns.length()];
26     }
27     // Baseline: enumerate unit-cost edit alternatives without memoization.
28     public static int baseline(String a, String b) {
29         validate(a, b);
30         return suffix(a, b, 0, 0);
31     }
32     private static int suffix(String a, String b, int i, int j) {
33         if (i == a.length()) return b.length() - j;
34         if (j == b.length()) return a.length() - i;
35         if (a.charAt(i) == b.charAt(j)) return suffix(a, b, i + 1, j + 1);
36         return 1 + Math.min(suffix(a, b, i + 1, j + 1), Math.min(suffix(a, b, i + 1, j), suffix(a, b, i, j + 1)));
37     }
38 }
39

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Choose the shorter column axis and initialize empty-prefix boundaries.
The displayed table includes the initialized first row/column: E(0,j)=j and E(i,0)=i. Interior nulls are uncomputed.
input
{"a":"ab","b":"ba"}
phase
"initial"
rows
"ab"
columns
"ba"
swapped
false
table
[[0,1,2],[1,null,null],[2,null,null]]
dp
[0,1,2]
Prepare the first column and the old diagonal for this row.
The left-to-right update mixes previous-row entries on the right with current-row entries on the left. The saved diagonal must survive until consumed.
input
{"a":"ab","b":"ba"}
phase
"row-start"
rows
"ab"
columns
"ba"
swapped
false
table
[[0,1,2],[1,null,null],[2,null,null]]
dp
[1,1,2]
i
1
j
0
diagonal
0
Read old up and diagonal together with the current left.
Match consumes both units for zero; mismatch compares substitution=oldDiagonal+1, deletion=up+1, and insertion=left+1 in displayed rows→columns orientation.
input
{"a":"ab","b":"ba"}
phase
"candidate"
rows
"ab"
columns
"ba"
swapped
false
table
[[0,1,2],[1,null,null],[2,null,null]]
dp
[1,1,2]
i
1
j
1
diagonal
0
oldDiagonal
0
up
1
left
1
equal
false
next
1
Write the cell and carry the saved old up as the next diagonal.
oldDiagonal retains the dependency used in this update; live diagonal now carries the old up for the next column. The new dp[j] must not become that next diagonal.
input
{"a":"ab","b":"ba"}
phase
"commit"
rows
"ab"
columns
"ba"
swapped
false
table
[[0,1,2],[1,1,null],[2,null,null]]
dp
[1,1,2]
i
1
j
1
diagonal
1
oldDiagonal
0
up
1
left
1
equal
false
next
1
Read old up and diagonal together with the current left.
Match consumes both units for zero; mismatch compares substitution=oldDiagonal+1, deletion=up+1, and insertion=left+1 in displayed rows→columns orientation.
input
{"a":"ab","b":"ba"}
phase
"candidate"
rows
"ab"
columns
"ba"
swapped
false
table
[[0,1,2],[1,1,null],[2,null,null]]
dp
[1,1,2]
i
1
j
2
diagonal
1
oldDiagonal
1
up
2
left
1
equal
true
next
1
Write the cell and carry the saved old up as the next diagonal.
oldDiagonal retains the dependency used in this update; live diagonal now carries the old up for the next column. The new dp[j] must not become that next diagonal.
input
{"a":"ab","b":"ba"}
phase
"commit"
rows
"ab"
columns
"ba"
swapped
false
table
[[0,1,2],[1,1,1],[2,null,null]]
dp
[1,1,1]
i
1
j
2
diagonal
2
oldDiagonal
1
up
2
left
1
equal
true
next
1
Prepare the first column and the old diagonal for this row.
The left-to-right update mixes previous-row entries on the right with current-row entries on the left. The saved diagonal must survive until consumed.
input
{"a":"ab","b":"ba"}
phase
"row-start"
rows
"ab"
columns
"ba"
swapped
false
table
[[0,1,2],[1,1,1],[2,null,null]]
dp
[2,1,1]
i
2
j
0
diagonal
1
Read old up and diagonal together with the current left.
Match consumes both units for zero; mismatch compares substitution=oldDiagonal+1, deletion=up+1, and insertion=left+1 in displayed rows→columns orientation.
input
{"a":"ab","b":"ba"}
phase
"candidate"
rows
"ab"
columns
"ba"
swapped
false
table
[[0,1,2],[1,1,1],[2,null,null]]
dp
[2,1,1]
i
2
j
1
diagonal
1
oldDiagonal
1
up
1
left
2
equal
true
next
1
Write the cell and carry the saved old up as the next diagonal.
oldDiagonal retains the dependency used in this update; live diagonal now carries the old up for the next column. The new dp[j] must not become that next diagonal.
input
{"a":"ab","b":"ba"}
phase
"commit"
rows
"ab"
columns
"ba"
swapped
false
table
[[0,1,2],[1,1,1],[2,1,null]]
dp
[2,1,1]
i
2
j
1
diagonal
1
oldDiagonal
1
up
1
left
2
equal
true
next
1
Read old up and diagonal together with the current left.
Match consumes both units for zero; mismatch compares substitution=oldDiagonal+1, deletion=up+1, and insertion=left+1 in displayed rows→columns orientation.
input
{"a":"ab","b":"ba"}
phase
"candidate"
rows
"ab"
columns
"ba"
swapped
false
table
[[0,1,2],[1,1,1],[2,1,null]]
dp
[2,1,1]
i
2
j
2
diagonal
1
oldDiagonal
1
up
1
left
1
equal
false
next
2
Write the cell and carry the saved old up as the next diagonal.
oldDiagonal retains the dependency used in this update; live diagonal now carries the old up for the next column. The new dp[j] must not become that next diagonal.
input
{"a":"ab","b":"ba"}
phase
"commit"
rows
"ab"
columns
"ba"
swapped
false
table
[[0,1,2],[1,1,1],[2,1,2]]
dp
[2,1,2]
i
2
j
2
diagonal
1
oldDiagonal
1
up
1
left
1
equal
false
next
2
Return the full-prefix score from the final row.
Unit insertion/deletion costs make the score symmetric even when axes are swapped. A returned edit script would need direction mapping and additional history.
input
{"a":"ab","b":"ba"}
phase
"complete"
rows
"ab"
columns
"ba"
swapped
false
table
[[0,1,2],[1,1,1],[2,1,2]]
dp
[2,1,2]
Return the documented result.
Displayed grids, snapshots and saved candidate annotations are teaching history, excluded from the Java implementation workspace. BigInteger counts use exact decimal strings in trace data.
result
2

Empty original source and swapped axes

Input: {"a":"","b":"abc"} · Unit-cost edit distance: 3

Step 1 of 6: Choose the shorter column axis and initialize empty-prefix boundaries.

The displayed table includes the initialized first row/column: E(0,j)=j and E(i,0)=i. Interior nulls are uncomputed.

Edit distance — unit-cost alignment and nonzero boundaries

Phase: initial.

Original inputs: {"a":"","b":"abc"}. Axes are swapped to keep the shorter string in columns. Operation labels below transform displayed rows → columns; unit-cost symmetry preserves the original distance.

Rows: "abc". Columns: "". Indices are prefix lengths measured in UTF-16 code units.

Conceptual edit cost grid — ∅ is an empty prefix; · is uncomputed
Row / column	0 — ∅
0 — ∅	0
1: "a"	1
2: "b"	2
3: "c"	3

Actual one-row Java buffer

dp[0]=0 — boundary/final row

State after this step
Variable	Value
input	`{"a":"","b":"abc"}`
phase	`"initial"`
rows	`"abc"`
columns	`""`
swapped	`true`
table	`[[0],[1],[2],[3]]`
dp	`[0]`

See the affected Java block

 1 import java.util.Objects;
 2 
 3 public final class Solution {
 4     private Solution() {}
 5     private static void validate(String a, String b) {
 6         Objects.requireNonNull(a, "a"); Objects.requireNonNull(b, "b");
 7         if (a.length() > 2_000 || b.length() > 2_000) throw new IllegalArgumentException("text too long");
 8     }
 9     public static int minDistance(String a, String b) {
10         validate(a, b);
11         String rows = a, columns = b;
12         if (columns.length() > rows.length()) { rows = b; columns = a; }
13         int[] dp = new int[columns.length() + 1];
14         for (int j = 0; j <= columns.length(); j++) dp[j] = j;
15         for (int i = 1; i <= rows.length(); i++) {
16             int diagonal = dp[0];
17             dp[0] = i;
18             for (int j = 1; j <= columns.length(); j++) {
19                 int up = dp[j];
20                 if (rows.charAt(i - 1) == columns.charAt(j - 1)) dp[j] = diagonal;
21                 else dp[j] = 1 + Math.min(diagonal, Math.min(up, dp[j - 1]));
22                 diagonal = up;
23             }
24         }
25         return dp[columns.length()];
26     }
27     // Baseline: enumerate unit-cost edit alternatives without memoization.
28     public static int baseline(String a, String b) {
29         validate(a, b);
30         return suffix(a, b, 0, 0);
31     }
32     private static int suffix(String a, String b, int i, int j) {
33         if (i == a.length()) return b.length() - j;
34         if (j == b.length()) return a.length() - i;
35         if (a.charAt(i) == b.charAt(j)) return suffix(a, b, i + 1, j + 1);
36         return 1 + Math.min(suffix(a, b, i + 1, j + 1), Math.min(suffix(a, b, i + 1, j), suffix(a, b, i, j + 1)));
37     }
38 }
39

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Choose the shorter column axis and initialize empty-prefix boundaries.
The displayed table includes the initialized first row/column: E(0,j)=j and E(i,0)=i. Interior nulls are uncomputed.
input
{"a":"","b":"abc"}
phase
"initial"
rows
"abc"
columns
""
swapped
true
table
[[0],[1],[2],[3]]
dp
[0]
Prepare the first column and the old diagonal for this row.
The left-to-right update mixes previous-row entries on the right with current-row entries on the left. The saved diagonal must survive until consumed.
input
{"a":"","b":"abc"}
phase
"row-start"
rows
"abc"
columns
""
swapped
true
table
[[0],[1],[2],[3]]
dp
[1]
i
1
j
0
diagonal
0
Prepare the first column and the old diagonal for this row.
The left-to-right update mixes previous-row entries on the right with current-row entries on the left. The saved diagonal must survive until consumed.
input
{"a":"","b":"abc"}
phase
"row-start"
rows
"abc"
columns
""
swapped
true
table
[[0],[1],[2],[3]]
dp
[2]
i
2
j
0
diagonal
1
Prepare the first column and the old diagonal for this row.
The left-to-right update mixes previous-row entries on the right with current-row entries on the left. The saved diagonal must survive until consumed.
input
{"a":"","b":"abc"}
phase
"row-start"
rows
"abc"
columns
""
swapped
true
table
[[0],[1],[2],[3]]
dp
[3]
i
3
j
0
diagonal
2
Return the full-prefix score from the final row.
Unit insertion/deletion costs make the score symmetric even when axes are swapped. A returned edit script would need direction mapping and additional history.
input
{"a":"","b":"abc"}
phase
"complete"
rows
"abc"
columns
""
swapped
true
table
[[0],[1],[2],[3]]
dp
[3]
Return the documented result.
Displayed grids, snapshots and saved candidate annotations are teaching history, excluded from the Java implementation workspace. BigInteger counts use exact decimal strings in trace data.
result
3

Repeated units preserve zero-cost matches

Input: {"a":"aaa","b":"aa"} · Unit-cost edit distance: 1

Step 1 of 18: Choose the shorter column axis and initialize empty-prefix boundaries.

The displayed table includes the initialized first row/column: E(0,j)=j and E(i,0)=i. Interior nulls are uncomputed.

Edit distance — unit-cost alignment and nonzero boundaries

Phase: initial.

Original inputs: {"a":"aaa","b":"aa"}. The shorter string is already in columns. Operation labels below transform displayed rows → columns; unit-cost symmetry preserves the original distance.

Rows: "aaa". Columns: "aa". Indices are prefix lengths measured in UTF-16 code units.

Conceptual edit cost grid — ∅ is an empty prefix; · is uncomputed
Row / column	0 — ∅	1: "a"	2: "a"
0 — ∅	0	1	2
1: "a"	1	·	·
2: "a"	2	·	·
3: "a"	3	·	·

Actual one-row Java buffer

dp[0]=0 — boundary/final row
dp[1]=1 — boundary/final row
dp[2]=2 — boundary/final row

State after this step
Variable	Value
input	`{"a":"aaa","b":"aa"}`
phase	`"initial"`
rows	`"aaa"`
columns	`"aa"`
swapped	`false`
table	`[[0,1,2],[1,null,null],[2,null,null],[3,null,null]]`
dp	`[0,1,2]`

See the affected Java block

 1 import java.util.Objects;
 2 
 3 public final class Solution {
 4     private Solution() {}
 5     private static void validate(String a, String b) {
 6         Objects.requireNonNull(a, "a"); Objects.requireNonNull(b, "b");
 7         if (a.length() > 2_000 || b.length() > 2_000) throw new IllegalArgumentException("text too long");
 8     }
 9     public static int minDistance(String a, String b) {
10         validate(a, b);
11         String rows = a, columns = b;
12         if (columns.length() > rows.length()) { rows = b; columns = a; }
13         int[] dp = new int[columns.length() + 1];
14         for (int j = 0; j <= columns.length(); j++) dp[j] = j;
15         for (int i = 1; i <= rows.length(); i++) {
16             int diagonal = dp[0];
17             dp[0] = i;
18             for (int j = 1; j <= columns.length(); j++) {
19                 int up = dp[j];
20                 if (rows.charAt(i - 1) == columns.charAt(j - 1)) dp[j] = diagonal;
21                 else dp[j] = 1 + Math.min(diagonal, Math.min(up, dp[j - 1]));
22                 diagonal = up;
23             }
24         }
25         return dp[columns.length()];
26     }
27     // Baseline: enumerate unit-cost edit alternatives without memoization.
28     public static int baseline(String a, String b) {
29         validate(a, b);
30         return suffix(a, b, 0, 0);
31     }
32     private static int suffix(String a, String b, int i, int j) {
33         if (i == a.length()) return b.length() - j;
34         if (j == b.length()) return a.length() - i;
35         if (a.charAt(i) == b.charAt(j)) return suffix(a, b, i + 1, j + 1);
36         return 1 + Math.min(suffix(a, b, i + 1, j + 1), Math.min(suffix(a, b, i + 1, j), suffix(a, b, i, j + 1)));
37     }
38 }
39

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Choose the shorter column axis and initialize empty-prefix boundaries.
The displayed table includes the initialized first row/column: E(0,j)=j and E(i,0)=i. Interior nulls are uncomputed.
input
{"a":"aaa","b":"aa"}
phase
"initial"
rows
"aaa"
columns
"aa"
swapped
false
table
[[0,1,2],[1,null,null],[2,null,null],[3,null,null]]
dp
[0,1,2]
Prepare the first column and the old diagonal for this row.
The left-to-right update mixes previous-row entries on the right with current-row entries on the left. The saved diagonal must survive until consumed.
input
{"a":"aaa","b":"aa"}
phase
"row-start"
rows
"aaa"
columns
"aa"
swapped
false
table
[[0,1,2],[1,null,null],[2,null,null],[3,null,null]]
dp
[1,1,2]
i
1
j
0
diagonal
0
Read old up and diagonal together with the current left.
Match consumes both units for zero; mismatch compares substitution=oldDiagonal+1, deletion=up+1, and insertion=left+1 in displayed rows→columns orientation.
input
{"a":"aaa","b":"aa"}
phase
"candidate"
rows
"aaa"
columns
"aa"
swapped
false
table
[[0,1,2],[1,null,null],[2,null,null],[3,null,null]]
dp
[1,1,2]
i
1
j
1
diagonal
0
oldDiagonal
0
up
1
left
1
equal
true
next
0
Write the cell and carry the saved old up as the next diagonal.
oldDiagonal retains the dependency used in this update; live diagonal now carries the old up for the next column. The new dp[j] must not become that next diagonal.
input
{"a":"aaa","b":"aa"}
phase
"commit"
rows
"aaa"
columns
"aa"
swapped
false
table
[[0,1,2],[1,0,null],[2,null,null],[3,null,null]]
dp
[1,0,2]
i
1
j
1
diagonal
1
oldDiagonal
0
up
1
left
1
equal
true
next
0
Read old up and diagonal together with the current left.
Match consumes both units for zero; mismatch compares substitution=oldDiagonal+1, deletion=up+1, and insertion=left+1 in displayed rows→columns orientation.
input
{"a":"aaa","b":"aa"}
phase
"candidate"
rows
"aaa"
columns
"aa"
swapped
false
table
[[0,1,2],[1,0,null],[2,null,null],[3,null,null]]
dp
[1,0,2]
i
1
j
2
diagonal
1
oldDiagonal
1
up
2
left
0
equal
true
next
1
Write the cell and carry the saved old up as the next diagonal.
oldDiagonal retains the dependency used in this update; live diagonal now carries the old up for the next column. The new dp[j] must not become that next diagonal.
input
{"a":"aaa","b":"aa"}
phase
"commit"
rows
"aaa"
columns
"aa"
swapped
false
table
[[0,1,2],[1,0,1],[2,null,null],[3,null,null]]
dp
[1,0,1]
i
1
j
2
diagonal
2
oldDiagonal
1
up
2
left
0
equal
true
next
1
Prepare the first column and the old diagonal for this row.
The left-to-right update mixes previous-row entries on the right with current-row entries on the left. The saved diagonal must survive until consumed.
input
{"a":"aaa","b":"aa"}
phase
"row-start"
rows
"aaa"
columns
"aa"
swapped
false
table
[[0,1,2],[1,0,1],[2,null,null],[3,null,null]]
dp
[2,0,1]
i
2
j
0
diagonal
1
Read old up and diagonal together with the current left.
Match consumes both units for zero; mismatch compares substitution=oldDiagonal+1, deletion=up+1, and insertion=left+1 in displayed rows→columns orientation.
input
{"a":"aaa","b":"aa"}
phase
"candidate"
rows
"aaa"
columns
"aa"
swapped
false
table
[[0,1,2],[1,0,1],[2,null,null],[3,null,null]]
dp
[2,0,1]
i
2
j
1
diagonal
1
oldDiagonal
1
up
0
left
2
equal
true
next
1
Write the cell and carry the saved old up as the next diagonal.
oldDiagonal retains the dependency used in this update; live diagonal now carries the old up for the next column. The new dp[j] must not become that next diagonal.
input
{"a":"aaa","b":"aa"}
phase
"commit"
rows
"aaa"
columns
"aa"
swapped
false
table
[[0,1,2],[1,0,1],[2,1,null],[3,null,null]]
dp
[2,1,1]
i
2
j
1
diagonal
0
oldDiagonal
1
up
0
left
2
equal
true
next
1
Read old up and diagonal together with the current left.
Match consumes both units for zero; mismatch compares substitution=oldDiagonal+1, deletion=up+1, and insertion=left+1 in displayed rows→columns orientation.
input
{"a":"aaa","b":"aa"}
phase
"candidate"
rows
"aaa"
columns
"aa"
swapped
false
table
[[0,1,2],[1,0,1],[2,1,null],[3,null,null]]
dp
[2,1,1]
i
2
j
2
diagonal
0
oldDiagonal
0
up
1
left
1
equal
true
next
0
Write the cell and carry the saved old up as the next diagonal.
oldDiagonal retains the dependency used in this update; live diagonal now carries the old up for the next column. The new dp[j] must not become that next diagonal.
input
{"a":"aaa","b":"aa"}
phase
"commit"
rows
"aaa"
columns
"aa"
swapped
false
table
[[0,1,2],[1,0,1],[2,1,0],[3,null,null]]
dp
[2,1,0]
i
2
j
2
diagonal
1
oldDiagonal
0
up
1
left
1
equal
true
next
0
Prepare the first column and the old diagonal for this row.
The left-to-right update mixes previous-row entries on the right with current-row entries on the left. The saved diagonal must survive until consumed.
input
{"a":"aaa","b":"aa"}
phase
"row-start"
rows
"aaa"
columns
"aa"
swapped
false
table
[[0,1,2],[1,0,1],[2,1,0],[3,null,null]]
dp
[3,1,0]
i
3
j
0
diagonal
2
Read old up and diagonal together with the current left.
Match consumes both units for zero; mismatch compares substitution=oldDiagonal+1, deletion=up+1, and insertion=left+1 in displayed rows→columns orientation.
input
{"a":"aaa","b":"aa"}
phase
"candidate"
rows
"aaa"
columns
"aa"
swapped
false
table
[[0,1,2],[1,0,1],[2,1,0],[3,null,null]]
dp
[3,1,0]
i
3
j
1
diagonal
2
oldDiagonal
2
up
1
left
3
equal
true
next
2
Write the cell and carry the saved old up as the next diagonal.
oldDiagonal retains the dependency used in this update; live diagonal now carries the old up for the next column. The new dp[j] must not become that next diagonal.
input
{"a":"aaa","b":"aa"}
phase
"commit"
rows
"aaa"
columns
"aa"
swapped
false
table
[[0,1,2],[1,0,1],[2,1,0],[3,2,null]]
dp
[3,2,0]
i
3
j
1
diagonal
1
oldDiagonal
2
up
1
left
3
equal
true
next
2
Read old up and diagonal together with the current left.
Match consumes both units for zero; mismatch compares substitution=oldDiagonal+1, deletion=up+1, and insertion=left+1 in displayed rows→columns orientation.
input
{"a":"aaa","b":"aa"}
phase
"candidate"
rows
"aaa"
columns
"aa"
swapped
false
table
[[0,1,2],[1,0,1],[2,1,0],[3,2,null]]
dp
[3,2,0]
i
3
j
2
diagonal
1
oldDiagonal
1
up
0
left
2
equal
true
next
1
Write the cell and carry the saved old up as the next diagonal.
oldDiagonal retains the dependency used in this update; live diagonal now carries the old up for the next column. The new dp[j] must not become that next diagonal.
input
{"a":"aaa","b":"aa"}
phase
"commit"
rows
"aaa"
columns
"aa"
swapped
false
table
[[0,1,2],[1,0,1],[2,1,0],[3,2,1]]
dp
[3,2,1]
i
3
j
2
diagonal
0
oldDiagonal
1
up
0
left
2
equal
true
next
1
Return the full-prefix score from the final row.
Unit insertion/deletion costs make the score symmetric even when axes are swapped. A returned edit script would need direction mapping and additional history.
input
{"a":"aaa","b":"aa"}
phase
"complete"
rows
"aaa"
columns
"aa"
swapped
false
table
[[0,1,2],[1,0,1],[2,1,0],[3,2,1]]
dp
[3,2,1]
Return the documented result.
Displayed grids, snapshots and saved candidate annotations are teaching history, excluded from the Java implementation workspace. BigInteger counts use exact decimal strings in trace data.
result
1

Nonzero first-column boundary

Input: {"a":"abc","b":"x"} · Unit-cost edit distance: 3

Step 1 of 12: Choose the shorter column axis and initialize empty-prefix boundaries.

The displayed table includes the initialized first row/column: E(0,j)=j and E(i,0)=i. Interior nulls are uncomputed.

Edit distance — unit-cost alignment and nonzero boundaries

Phase: initial.

Original inputs: {"a":"abc","b":"x"}. The shorter string is already in columns. Operation labels below transform displayed rows → columns; unit-cost symmetry preserves the original distance.

Rows: "abc". Columns: "x". Indices are prefix lengths measured in UTF-16 code units.

Conceptual edit cost grid — ∅ is an empty prefix; · is uncomputed
Row / column	0 — ∅	1: "x"
0 — ∅	0	1
1: "a"	1	·
2: "b"	2	·
3: "c"	3	·

Actual one-row Java buffer

dp[0]=0 — boundary/final row
dp[1]=1 — boundary/final row

State after this step
Variable	Value
input	`{"a":"abc","b":"x"}`
phase	`"initial"`
rows	`"abc"`
columns	`"x"`
swapped	`false`
table	`[[0,1],[1,null],[2,null],[3,null]]`
dp	`[0,1]`

See the affected Java block

 1 import java.util.Objects;
 2 
 3 public final class Solution {
 4     private Solution() {}
 5     private static void validate(String a, String b) {
 6         Objects.requireNonNull(a, "a"); Objects.requireNonNull(b, "b");
 7         if (a.length() > 2_000 || b.length() > 2_000) throw new IllegalArgumentException("text too long");
 8     }
 9     public static int minDistance(String a, String b) {
10         validate(a, b);
11         String rows = a, columns = b;
12         if (columns.length() > rows.length()) { rows = b; columns = a; }
13         int[] dp = new int[columns.length() + 1];
14         for (int j = 0; j <= columns.length(); j++) dp[j] = j;
15         for (int i = 1; i <= rows.length(); i++) {
16             int diagonal = dp[0];
17             dp[0] = i;
18             for (int j = 1; j <= columns.length(); j++) {
19                 int up = dp[j];
20                 if (rows.charAt(i - 1) == columns.charAt(j - 1)) dp[j] = diagonal;
21                 else dp[j] = 1 + Math.min(diagonal, Math.min(up, dp[j - 1]));
22                 diagonal = up;
23             }
24         }
25         return dp[columns.length()];
26     }
27     // Baseline: enumerate unit-cost edit alternatives without memoization.
28     public static int baseline(String a, String b) {
29         validate(a, b);
30         return suffix(a, b, 0, 0);
31     }
32     private static int suffix(String a, String b, int i, int j) {
33         if (i == a.length()) return b.length() - j;
34         if (j == b.length()) return a.length() - i;
35         if (a.charAt(i) == b.charAt(j)) return suffix(a, b, i + 1, j + 1);
36         return 1 + Math.min(suffix(a, b, i + 1, j + 1), Math.min(suffix(a, b, i + 1, j), suffix(a, b, i, j + 1)));
37     }
38 }
39

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Choose the shorter column axis and initialize empty-prefix boundaries.
The displayed table includes the initialized first row/column: E(0,j)=j and E(i,0)=i. Interior nulls are uncomputed.
input
{"a":"abc","b":"x"}
phase
"initial"
rows
"abc"
columns
"x"
swapped
false
table
[[0,1],[1,null],[2,null],[3,null]]
dp
[0,1]
Prepare the first column and the old diagonal for this row.
The left-to-right update mixes previous-row entries on the right with current-row entries on the left. The saved diagonal must survive until consumed.
input
{"a":"abc","b":"x"}
phase
"row-start"
rows
"abc"
columns
"x"
swapped
false
table
[[0,1],[1,null],[2,null],[3,null]]
dp
[1,1]
i
1
j
0
diagonal
0
Read old up and diagonal together with the current left.
Match consumes both units for zero; mismatch compares substitution=oldDiagonal+1, deletion=up+1, and insertion=left+1 in displayed rows→columns orientation.
input
{"a":"abc","b":"x"}
phase
"candidate"
rows
"abc"
columns
"x"
swapped
false
table
[[0,1],[1,null],[2,null],[3,null]]
dp
[1,1]
i
1
j
1
diagonal
0
oldDiagonal
0
up
1
left
1
equal
false
next
1
Write the cell and carry the saved old up as the next diagonal.
oldDiagonal retains the dependency used in this update; live diagonal now carries the old up for the next column. The new dp[j] must not become that next diagonal.
input
{"a":"abc","b":"x"}
phase
"commit"
rows
"abc"
columns
"x"
swapped
false
table
[[0,1],[1,1],[2,null],[3,null]]
dp
[1,1]
i
1
j
1
diagonal
1
oldDiagonal
0
up
1
left
1
equal
false
next
1
Prepare the first column and the old diagonal for this row.
The left-to-right update mixes previous-row entries on the right with current-row entries on the left. The saved diagonal must survive until consumed.
input
{"a":"abc","b":"x"}
phase
"row-start"
rows
"abc"
columns
"x"
swapped
false
table
[[0,1],[1,1],[2,null],[3,null]]
dp
[2,1]
i
2
j
0
diagonal
1
Read old up and diagonal together with the current left.
Match consumes both units for zero; mismatch compares substitution=oldDiagonal+1, deletion=up+1, and insertion=left+1 in displayed rows→columns orientation.
input
{"a":"abc","b":"x"}
phase
"candidate"
rows
"abc"
columns
"x"
swapped
false
table
[[0,1],[1,1],[2,null],[3,null]]
dp
[2,1]
i
2
j
1
diagonal
1
oldDiagonal
1
up
1
left
2
equal
false
next
2
Write the cell and carry the saved old up as the next diagonal.
oldDiagonal retains the dependency used in this update; live diagonal now carries the old up for the next column. The new dp[j] must not become that next diagonal.
input
{"a":"abc","b":"x"}
phase
"commit"
rows
"abc"
columns
"x"
swapped
false
table
[[0,1],[1,1],[2,2],[3,null]]
dp
[2,2]
i
2
j
1
diagonal
1
oldDiagonal
1
up
1
left
2
equal
false
next
2
Prepare the first column and the old diagonal for this row.
The left-to-right update mixes previous-row entries on the right with current-row entries on the left. The saved diagonal must survive until consumed.
input
{"a":"abc","b":"x"}
phase
"row-start"
rows
"abc"
columns
"x"
swapped
false
table
[[0,1],[1,1],[2,2],[3,null]]
dp
[3,2]
i
3
j
0
diagonal
2
Read old up and diagonal together with the current left.
Match consumes both units for zero; mismatch compares substitution=oldDiagonal+1, deletion=up+1, and insertion=left+1 in displayed rows→columns orientation.
input
{"a":"abc","b":"x"}
phase
"candidate"
rows
"abc"
columns
"x"
swapped
false
table
[[0,1],[1,1],[2,2],[3,null]]
dp
[3,2]
i
3
j
1
diagonal
2
oldDiagonal
2
up
2
left
3
equal
false
next
3
Write the cell and carry the saved old up as the next diagonal.
oldDiagonal retains the dependency used in this update; live diagonal now carries the old up for the next column. The new dp[j] must not become that next diagonal.
input
{"a":"abc","b":"x"}
phase
"commit"
rows
"abc"
columns
"x"
swapped
false
table
[[0,1],[1,1],[2,2],[3,3]]
dp
[3,3]
i
3
j
1
diagonal
2
oldDiagonal
2
up
2
left
3
equal
false
next
3
Return the full-prefix score from the final row.
Unit insertion/deletion costs make the score symmetric even when axes are swapped. A returned edit script would need direction mapping and additional history.
input
{"a":"abc","b":"x"}
phase
"complete"
rows
"abc"
columns
"x"
swapped
false
table
[[0,1],[1,1],[2,2],[3,3]]
dp
[3,3]
Return the documented result.
Displayed grids, snapshots and saved candidate annotations are teaching history, excluded from the Java implementation workspace. BigInteger counts use exact decimal strings in trace data.
result
3

Test the contract

Input: a="abc", b="abc"
Output: 0
All zero-cost matches.
Input: a="abc", b=""
Output: 3
Delete each source unit.
Input: a="abc", b="xyz"
Output: 3
Three substitutions.
Input: a="aaa", b="aa"
Output: 1
One deletion; repeated units are distinct occurrences.
Input: a="😀", b=""
Output: 2
The unit is UTF-16, not a supplementary code point.
Input: a=null, b=""
Output: NullPointerException
Validation comes before base cases.

Common mistakes and counterexamples

Use LCS mismatch logic or insertion/deletion-only identity

Counterexample: a→b costs one substitution, but m+n−2LCS gives two.

Include a cost-one substitution from the diagonal.

Set the first row and column to zero

Counterexample: Empty→abc must cost three, rather than zero.

Initialize lengths as insertion/deletion boundary costs.

Treat transposition as one operation

Counterexample: ab→ba has distance two under this contract.

Use a different recurrence and contract for Damerau-style transposition.

Overwrite diagonal or silently change Unicode units

Counterexample: Saving the new dp[j] as diagonal reuses an updated cost; deleting 😀 is two code-unit deletions here.

Save old up before writing, carry it afterward, and state the text unit explicitly.

Follow-ups

Return one edit script.

Retain a full grid or use divide-and-conquer reconstruction and follow optimum-preserving predecessor choices. Define tie priorities, occurrence positions, and application order carefully because edits shift indices. If the score computation swapped axes, invert insertion/deletion direction and map positions back to the original source.

Use unequal or weighted edit costs.

Replace each candidate with its operation-specific cost and choose a sufficiently wide numeric type. Base rows accumulate insertion costs and base columns deletion costs. Distance may become asymmetric when insertion and deletion differ, so shorter-axis swapping needs corresponding cost transposition rather than a blind reference swap.

Only determine whether distance is at most k.

The length difference is a lower bound. For small k, evaluate an appropriate diagonal band and cap unreachable/out-of-band values above k. A complete row with all feasible costs above the threshold can support safe rejection under a proved band invariant. Do not return early just because one intermediate cell exceeds k.

Related foundations

Dynamic programming: state before recurrence

Keep practicing

Return to the lesson

AceYourInterviews · 2026-10-17 · Original teaching content and implementations authored for AceYourInterviews. Familiar interview problem names describe standard algorithmic tasks; no company-frequency or platform-difficulty claims are made.