Definition
- Edit Distance (Levenshtein distance) – the minimum number of single-character insertions, deletions, and substitutions to transform one string into another.
- 2D DP table –
dp[i][j]stores the minimum edits for the firsticharacters of A and the firstjcharacters of B. - Match rule – if characters are equal, no edit is needed:
dp[i][j] = dp[i-1][j-1]. - Mismatch rule – take 1 + min of substitute (diagonal), delete (top), insert (left).
- Base cases –
dp[i][0] = i(pure deletions) anddp[0][j] = j(pure insertions).
At the National Bank of India, Rajesh types a beneficiary name during a transfer. The system measures how many single-character edits separate the typed name from the registered name. A small distance suggests a harmless typo, while a large distance flags a wrong beneficiary.
Understanding the Concepts
What is the Edit Distance problem?
Edit Distance (Levenshtein distance) asks for the minimum number of single-character operations needed to transform one string into another. The allowed operations are: insert a character, delete a character, and substitute a character. For example, transforming "KITTEN" into "SITTING" requires 3 edits.
package com.bank.core;
// "KITTEN" -> "SITTING"
// Step 1: substitute K -> S: "SITTEN"
// Step 2: substitute E -> I: "SITTIN"
// Step 3: insert G at end: "SITTING"
// Edit distance = 3
How does the 2D DP table work?
Define dp[i][j] as the minimum edits to transform the first i characters of A into the first j characters of B. The base cases handle transforming to or from an empty string: dp[i][0] = i (delete all i characters) and dp[0][j] = j (insert all j characters). For the rest of the table, if the characters match, no edit is needed and the cell copies the diagonal. If they differ, you consider three operations and take the cheapest.
package com.bank.service;
public class EditDistance {
public int minDistance(String a, String b) {
int m = a.length();
int n = b.length();
int[][] dp = new int[m + 1][n + 1];
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 (a.charAt(i - 1) == b.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1]; // no edit
} else {
dp[i][j] = 1 + Math.min(
dp[i - 1][j - 1], // substitute
Math.min(
dp[i - 1][j], // delete from A
dp[i][j - 1] // insert into A
)
);
}
}
}
return dp[m][n];
}
public static void main(String[] args) {
EditDistance solver = new EditDistance();
System.out.println(solver.minDistance("KITTEN", "SITTING"));
System.out.println(solver.minDistance("SALARY", "SLARY"));
}
}
3
1
What do the three mismatch operations mean?
When characters differ, you have three choices. Substitute replaces A[i] with B[j], costing 1 edit plus whatever it took to match the prefixes before both characters (diagonal dp[i-1][j-1]). Delete removes A[i] from A, costing 1 plus the cost of matching A[1..i-1] with B[1..j] (top dp[i-1][j]). Insert adds B[j] to A, costing 1 plus the cost of matching A[1..i] with B[1..j-1] (left dp[i][j-1]).
package com.bank.core;
// On mismatch at dp[i][j]:
// Substitute: dp[i-1][j-1] + 1 (replace A[i] with B[j], move diagonal)
// Delete: dp[i-1][j] + 1 (remove A[i], move up)
// Insert: dp[i][j-1] + 1 (add B[j] to A, move left)
// Take the minimum of all three
How do you optimize space with rolling rows?
Since each row depends only on the previous row and the current row's earlier cells, you can use two 1D arrays. This reduces space from O(m * n) to O(min(m, n)) by choosing the shorter string as the column dimension.
package com.bank.service;
public class EditDistanceOptimized {
public int minDistance(String a, String b) {
if (a.length() < b.length()) {
String temp = a; a = b; b = temp;
}
int m = a.length();
int n = b.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 (a.charAt(i - 1) == b.charAt(j - 1)) {
curr[j] = prev[j - 1];
} else {
curr[j] = 1 + Math.min(prev[j - 1],
Math.min(prev[j], curr[j - 1]));
}
}
int[] temp = prev;
prev = curr;
curr = temp;
}
return prev[n];
}
}
How is Edit Distance related to LCS?
When only insertions and deletions are allowed (no substitutions), the minimum edit distance equals m + n - 2 * LCS. Adding substitution as a third operation makes edit distance strictly smaller or equal: a substitution replaces what would otherwise be a deletion followed by an insertion.
| Problem | Operations | Formula |
|---|---|---|
| Edit distance (Levenshtein) | Insert, delete, substitute | Own recurrence |
| Insert/delete-only distance | Insert, delete | m + n - 2 * LCS |
| LCS | N/A | dp[m][n] from LCS table |
| SCS | N/A | m + n - LCS |
package com.bank.core;
// With substitution: edit("ABC", "AEC") = 1 (substitute B->E)
// Without substitution: edit("ABC", "AEC") = 2 (delete B, insert E)
// Substitution saves one step when both strings differ at one position
What are the edge cases?
Edge cases include: one or both strings empty, both strings identical (distance 0), strings of different lengths, and strings with no common characters.
package com.bank.core;
// Edge case 1: A="", B="ABC" -> 3 (insert A, B, C)
// Edge case 2: A="ABC", B="" -> 3 (delete A, B, C)
// Edge case 3: A=B="SAME" -> 0 (no edits needed)
// Edge case 4: A="AB", B="CD" -> 2 (substitute each)
// Edge case 5: A="A", B="A" -> 0
What about a banking use case?
At the National Bank of India, the transfer system compares a typed beneficiary name against the registered name. A small edit distance suggests a harmless typo that can proceed with a warning, while a large distance blocks the transfer as a potential wrong beneficiary.
package com.bank.service;
public class BeneficiaryValidator {
private final EditDistance editDistance = new EditDistance();
public String validateBeneficiary(String typed, String registered) {
int distance = editDistance.minDistance(
typed.toUpperCase(), registered.toUpperCase());
if (distance == 0) {
return "EXACT MATCH";
} else if (distance <= 2) {
return "LIKELY TYPO (distance=" + distance + "), proceed with warning";
} else {
return "MISMATCH (distance=" + distance + "), block transfer";
}
}
public static void main(String[] args) {
BeneficiaryValidator validator = new BeneficiaryValidator();
System.out.println(validator.validateBeneficiary("RAJSH", "RAJESH"));
System.out.println(validator.validateBeneficiary("PRIYA", "PRIYA"));
System.out.println(validator.validateBeneficiary("KUMAR", "RAJESH"));
}
}
LIKELY TYPO (distance=1), proceed with warning
EXACT MATCH
MISMATCH (distance=5), block transfer
What are common mistakes?
The most common mistake is forgetting to initialize the base cases. Without dp[i][0] = i and dp[0][j] = j, the border cells default to zero and the entire computation produces wrong results. Another mistake is using the wrong cell for substitution (using top or left instead of diagonal).
package com.bank.core;
// WRONG: missing base cases
int[][] dp = new int[m + 1][n + 1]; // all zeros!
// dp[3][0] should be 3, not 0
// CORRECT: explicit base case initialization
for (int i = 0; i <= m; i++) dp[i][0] = i;
for (int j = 0; j <= n; j++) dp[0][j] = j;
What should a senior engineer know?
A senior engineer should know that Edit Distance has no known sub-quadratic worst-case algorithm, and the SETH conjecture suggests O(n^2) may be a hard lower bound. For production fuzzy matching on large dictionaries, approximate algorithms or BK-trees are used to avoid computing edit distance against every entry. The rolling-row optimization is essential for long strings, and Hirschberg's algorithm combines linear space with the ability to reconstruct the edit sequence.
package com.bank.core;
// Senior notes:
// 1. No known sub-quadratic worst-case algorithm
// 2. SETH conjecture: O(n^2) may be a hard lower bound
// 3. BK-trees: index words by edit distance for fast fuzzy search
// 4. Hirschberg: linear space + full reconstruction
// 5. Applications: spell check, DNA alignment, fuzzy matching
Visual Overview
Edit Distance table for A = "SAL" and B = "SLRY":
"" S L R Y
"" [ 0 1 2 3 4 ]
S [ 1 0 1 2 3 ]
A [ 2 1 1 2 3 ]
L [ 3 2 1 2 3 ]
Answer: dp[3][4] = 3
Fill rules:
┌─────────────────────────────────────────┐
│ If A[i-1] == B[j-1]: │
│ dp[i][j] = dp[i-1][j-1] │
│ (match, no edit needed) │
│ │
│ If A[i-1] != B[j-1]: │
│ dp[i][j] = 1 + min( │
│ dp[i-1][j-1], <- substitute │
│ dp[i-1][j], <- delete from A │
│ dp[i][j-1] <- insert into A │
│ ) │
└─────────────────────────────────────────┘
Base cases:
┌─────────────────────────────────────────┐
│ dp[i][0] = i (delete i characters) │
│ dp[0][j] = j (insert j characters) │
└─────────────────────────────────────────┘
Three operations visualized:
dp[i-1][j-1] ──substitute──→ dp[i][j]
│ ↑
│ │
dp[i-1][j] ────delete────→ dp[i][j]
↑
dp[i][j-1] ────insert────→ dp[i][j]
Key Takeaway
Edit Distance, also called Levenshtein distance, measures the minimum number of single-character insertions, deletions, and substitutions needed to transform one string into another. You define dp[i][j] as the minimum edits to transform the first i characters of A into the first j characters of B. The base cases are straightforward: turning a prefix into empty requires that many deletions, and building a prefix from empty requires that many insertions.
Inside the table, when characters match, no edit is needed and the cell copies the diagonal. When they differ, you consider three operations and take the cheapest: substitute costs 1 plus the diagonal, delete costs 1 plus the cell above, and insert costs 1 plus the cell to the left. The answer is at dp[m][n]. Space reduces to O(min(m, n)) with two rolling rows.
Edit distance generalizes the insert/delete-only problem (which equals m + n - 2 * LCS) by adding substitution as a third operation. It belongs to the Longest Common Substring pattern family alongside LCS and SCS. For production use, BK-trees index words by edit distance for fast fuzzy search, and Hirschberg's algorithm achieves linear space with full reconstruction.
At the National Bank of India, Rajesh used edit distance to compare typed beneficiary names against registered names during fund transfers. A small distance meant a harmless typo that could proceed with a warning, while a large distance flagged a potential wrong beneficiary and blocked the transfer. The rolling-row optimization kept memory manageable for long names.
Remember one sentence: on a match copy the diagonal, on a mismatch add one to the minimum of substitute, delete, or insert.
---