Definition
- Edit distance – the minimum number of single-character operations (insert, delete, replace) to transform one string into another.
- Levenshtein distance – the standard variant where all three operations cost one.
- DP table –
dp[i][j]stores the edit distance between the firsticharacters of string A and firstjcharacters of string B. - Match rule – if
A[i-1] == B[j-1], copy the diagonal:dp[i][j] = dp[i-1][j-1]. - Mismatch rule –
dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])for delete, insert, replace. - Complexity – O(m * n) time and space, reducible to O(min(m, n)) space with two rolling rows.
The data-quality team at National Bank of India must fix a mistyped account holder name like RAJHES into the official spelling RAJESH using the fewest single-letter edits. If the current letters agree, no edit is needed there; if they differ, pick the cheapest of deleting a letter, inserting the correct letter, or replacing the wrong letter.
Understanding the Concepts
What is edit distance?
Edit distance, also called Levenshtein distance, measures how different two strings are by counting the minimum number of single-character operations needed to transform one string into the other. The three allowed operations are:
- Insert a character into string A.
- Delete a character from string A.
- Replace a character in string A with a different character.
For example, transforming "KITTEN" into "SITTING" requires three operations: replace K with S, replace E with I, insert G at the end.
package com.bank.dsa;
public class EditDistanceBasic {
public static int editDistance(String a, String b) {
int m = a.length(), n = b.length();
int[][] dp = new int[m + 1][n + 1];
// Base cases: transforming a prefix to/from empty string
for (int i = 0; i <= m; i++) dp[i][0] = i; // i deletions
for (int j = 0; j <= n; j++) dp[0][j] = j; // j insertions
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]; // match: no operation needed
} else {
dp[i][j] = 1 + Math.min(
dp[i - 1][j - 1], // replace
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) {
System.out.println(editDistance("RAJHES", "RAJESH")); // 2
System.out.println(editDistance("KITTEN", "SITTING")); // 3
}
}
2
3
Why does edit distance exist?
Edit distance exists because exact string matching is too rigid for real-world data. Account holder names in banking systems have typos, abbreviations, and transliteration differences. A customer named RAJESH might appear as RAJHES, RAJSH, or RAJESSH in different records. Edit distance quantifies how close two strings are, enabling fuzzy matching with a threshold.
It is also the foundation of diff tools, spell-checkers, DNA sequence alignment, and plagiarism detection.
How does the DP table work internally?
The table has (m + 1) rows and (n + 1) columns, where m and n are the lengths of the two strings. Cell dp[i][j] represents the edit distance between the first i characters of A and the first j characters of B.
The first column dp[i][0] is i, because transforming a prefix of length i into an empty string requires i deletions. The first row dp[0][j] is j, because building a prefix of length j from an empty string requires j insertions.
For the body, when A[i-1] == B[j-1], the current characters match and no operation is needed, so dp[i][j] equals the diagonal dp[i-1][j-1]. When they differ, we take 1 plus the minimum of three neighbours:
- dp[i-1][j-1] represents replace: change A[i-1] to B[j-1] and solve the rest.
- dp[i-1][j] represents delete: remove A[i-1] and match the remaining prefix.
- dp[i][j-1] represents insert: insert B[j-1] into A and match the remaining suffix.
package com.bank.dsa;
public class EditDistanceTablePrint {
public static void printTable(String a, String b) {
int m = a.length(), 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++)
dp[i][j] = a.charAt(i - 1) == b.charAt(j - 1)
? dp[i - 1][j - 1]
: 1 + Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1]));
// Print the table
System.out.print(" ");
for (int j = 0; j <= n; j++)
System.out.printf("%3s", j == 0 ? "_" : String.valueOf(b.charAt(j - 1)));
System.out.println();
for (int i = 0; i <= m; i++) {
System.out.printf("%3s", i == 0 ? "_" : String.valueOf(a.charAt(i - 1)));
for (int j = 0; j <= n; j++)
System.out.printf("%3d", dp[i][j]);
System.out.println();
}
}
public static void main(String[] args) {
printTable("ACE", "ABCE");
}
}
_ A B C E
_ 0 1 2 3 4
A 1 0 1 2 3
C 2 1 1 1 2
E 3 2 2 2 1
How do you optimise space to two rows?
Each cell dp[i][j] depends only on three cells: dp[i-1][j-1] (diagonal), dp[i-1][j] (above), and dp[i][j-1] (left). This means each row depends only on the previous row. We can keep just two arrays and alternate between them.
package com.bank.dsa;
public class EditDistanceSpaceOptimised {
public static int editDistance(String a, String b) {
int m = a.length(), n = b.length();
// Use the shorter string as columns for minimal space
if (m < n) return editDistance(b, a);
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];
}
public static void main(String[] args) {
System.out.println(editDistance("RAJHES", "RAJESH")); // 2
}
}
2
How is edit distance different from longest common subsequence?
| Aspect | Edit Distance | Longest Common Subsequence |
|---|---|---|
| Goal | Minimise operations to transform A into B | Maximise the length of matching elements |
| Operations | Insert, delete, replace | No explicit operations, just matching |
| Table meaning | dp[i][j] = min edits | dp[i][j] = max common length |
| Match case | dp[i][j] = dp[i-1][j-1] | dp[i][j] = dp[i-1][j-1] + 1 |
| Mismatch case | 1 + min of three neighbours | max of two neighbours |
| Relationship | edit distance = m + n - 2 * LCS when only insert and delete are allowed |
When the replace operation is removed (only insert and delete allowed), edit distance equals m + n - 2 * LCS(A, B). This connection helps verify solutions.
What are common mistakes?
The most frequent mistake is indexing. The DP table is (m+1) by (n+1) but the string characters are zero-indexed. When filling dp[i][j], you compare a.charAt(i - 1) with b.charAt(j - 1), not a.charAt(i) with b.charAt(j).
// WRONG: off-by-one indexing
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
if (a.charAt(i) == b.charAt(j)) // ArrayIndexOutOfBoundsException when i == m
dp[i][j] = dp[i - 1][j - 1];
// CORRECT: use i-1 and j-1 for character access
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];
Another mistake is forgetting the border initialisation. Without dp[i][0] = i and dp[0][j] = j, the table starts with all zeros and produces incorrect results.
What are edge cases?
When one string is empty, the edit distance is the length of the other string. When both strings are identical, the distance is zero. When one string is a single character, the distance is either the other string's length minus one (if the character appears in it) or the other string's length.
package com.bank.dsa;
public class EditDistanceEdgeCases {
public static void main(String[] args) {
System.out.println(EditDistanceBasic.editDistance("", "RAJESH")); // 6
System.out.println(EditDistanceBasic.editDistance("RAJESH", "")); // 6
System.out.println(EditDistanceBasic.editDistance("RAJESH", "RAJESH")); // 0
System.out.println(EditDistanceBasic.editDistance("A", "ABCDE")); // 4
}
}
6
6
0
4
When should you use edit distance in banking?
Edit distance is used in KYC (Know Your Customer) name matching. When a customer submits a name that does not exactly match the official record, the system computes the edit distance. If the distance is below a threshold (for example, two edits for names under ten characters), the system flags it as a likely typo rather than a different person.
package com.bank.service;
public class KycNameMatcher {
public static boolean isFuzzyMatch(String submitted, String official, int threshold) {
int distance = editDistance(submitted.toUpperCase(), official.toUpperCase());
return distance <= threshold;
}
private static int editDistance(String a, String b) {
int m = a.length(), n = b.length();
int[] prev = new int[n + 1], 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++)
curr[j] = a.charAt(i - 1) == b.charAt(j - 1)
? prev[j - 1]
: 1 + Math.min(prev[j - 1], Math.min(prev[j], curr[j - 1]));
int[] t = prev; prev = curr; curr = t;
}
return prev[n];
}
public static void main(String[] args) {
System.out.println(isFuzzyMatch("RAJHES", "RAJESH", 2)); // true
System.out.println(isFuzzyMatch("PANKAJ", "RAJESH", 2)); // false
System.out.println(isFuzzyMatch("RAJESSH", "RAJESH", 1)); // true
}
}
true
false
true
What should a senior engineer know?
A senior engineer should know that weighted edit distance assigns different costs to different operations. In name matching, a substitution between phonetically similar characters (S and SH) might cost less than a substitution between unrelated characters. This produces a generalised Levenshtein distance.
The Damerau-Levenshtein variant adds transposition (swapping two adjacent characters) as a fourth operation, which catches common typing errors more accurately.
For very long strings, approximate algorithms or banded edit distance (computing only a diagonal band of width k around the main diagonal) reduce the time from O(m * n) to O(m * k) when you only care about distances below a threshold k.
Visual Overview
Edit Distance DP Table for "ACE" → "ABCE"
──────────────────────────────────────────
_ A B C E
_ 0 1 2 3 4
A 1 [0] 1 2 3
C 2 1 1 [1] 2
E 3 2 2 2 [1] ← answer
Legend:
[x] = match, copied from diagonal
Others = 1 + min(diagonal, above, left)
Three operations at each mismatch:
┌─────────┐
│ dp[i-1] │ dp[i-1] ← delete (cell above)
│ [j-1] │ [j]
│ replace │
├─────────┤
│ dp[i] │ dp[i][j] ← current cell
│ [j-1] │
│ insert │
└─────────┘
Key Takeaway
Edit Distance, also called Levenshtein distance, is a two-dimensional dynamic programming problem that measures how many single-character insertions, deletions, or replacements are needed to transform one string into another. The DP table has (m + 1) rows and (n + 1) columns, and the borders are the base cases: turning a prefix of length i into an empty string requires i deletions, and building a prefix of length j from nothing requires j insertions.
The body of the table follows two simple rules. When the current characters match, copy the diagonal cell because no operation is needed. When they differ, take 1 plus the minimum of three neighbours: the diagonal is a replacement, the cell above is a deletion, and the cell to the left is an insertion. The answer sits in the bottom-right corner. Space drops from O(m * n) to O(min(m, n)) by keeping only two rolling rows, since each row depends only on the one before it.
At the National Bank of India, the KYC team used edit distance to match customer-submitted names against official records. A name like RAJHES was within two edits of RAJESH, so the system flagged it as a likely typo rather than a different person. The same technique powers spell-checkers and diff tools across the industry.
The senior-level addition is that weighted edit distance assigns different costs to different operations, and the Damerau-Levenshtein variant adds transposition as a fourth operation. For long strings where you only care about small distances, banded edit distance computes only a narrow diagonal strip and runs much faster.
Remember one sentence: on a match copy the diagonal, on a mismatch take 1 plus the minimum of three neighbours for delete, insert, and replace.
---