Levenshtein (Edit) Distance Explained with Examples

The Levenshtein distance between two strings is the smallest number of single-character edits — insertions, deletions, or substitutions — needed to turn one string into the other. It is the number behind spell-checkers, fuzzy search, and the "did you mean?" suggestions you see every day. The classic example: turning kitten into sitting takes exactly three edits, so their Levenshtein distance is 3. This guide explains where that number comes from, how the dynamic-programming solution computes it step by step, and how it relates to the diff algorithms behind text comparison.

The Three Edits That Count

Levenshtein distance allows exactly three operations, and each one costs 1:

• Insertion — add a character. sittin → sitting (add "g").
• Deletion — remove a character. caat → cat (drop one "a").
• Substitution — swap one character for another. kitten → sitten (replace "k" with "s").

The distance is the minimum total cost to get from one string to the other. "Minimum" is the important word: there are countless ways to edit one word into another, but the Levenshtein distance is the cheapest possible path.

The Classic Example: kitten to sitting

Watch how three edits transform one word into the other:

1. kitten → sitten — substitute k with s
2. sitten → sittin — substitute e with i
3. sittin → sitting — insert g at the end

Three edits, and you cannot do it in fewer. That is why the Levenshtein distance of kitten and sitting is 3. The obvious question is: how does a computer find that minimum without trying every possible sequence of edits? The answer is a dynamic-programming table.

Computing It with a Dynamic Programming Matrix

Trying every possible edit path is exponential and pointless. Instead we build a matrix where each cell solves a smaller version of the problem and reuses the answers already computed. Let the rows represent kitten and the columns represent sitting. Cell D[i][j] holds the edit distance between the first i letters of the first word and the first j letters of the second.

Two things seed the table. The first row counts up from 0 (turning an empty string into "sitting" takes one insertion per letter), and the first column does the same (turning "kitten" into an empty string takes one deletion per letter). Every other cell follows one short rule:

if letters match:
    D[i][j] = D[i-1][j-1]                      # no edit needed, copy the diagonal
else:
    D[i][j] = 1 + min( D[i-1][j],     # deletion
                       D[i][j-1],     # insertion
                       D[i-1][j-1] )  # substitution

When the two current letters match, you carry the diagonal value straight down with no added cost. When they differ, you take the cheapest of the three neighbors and add 1 for the edit. Fill the grid left to right, top to bottom, and the bottom-right cell holds the answer:

The value in the bottom-right corner is 3 — the Levenshtein distance. Following the highlighted path backward reconstructs the actual edits: the two substitutions (k→s, e→i) and the one insertion (g).

Time and Space Complexity

The matrix has (m+1) × (n+1) cells for strings of length m and n, and each cell is filled in constant time:

If you only need the distance number and not the list of edits, you can keep just the current and previous rows, dropping memory to O(min(m, n)). You need the full matrix only when you want to trace back the exact operations.

Levenshtein vs. Longest Common Subsequence

Levenshtein distance and the longest common subsequence (LCS) are close cousins — both are dynamic-programming problems on two strings, filled with almost the same kind of grid — but they measure different things.

• LCS counts what the two strings have in common (the longest shared, in-order run). It is the basis of most diff tools, where the LCS is the "unchanged" part.
• Levenshtein counts how far apart the two strings are (the fewest edits between them). It is the basis of similarity scores and fuzzy matching.

They are related: if substitutions were banned and only insertions and deletions were allowed, the edit distance would equal m + n − 2 × LCS. That is why LCS powers "what changed" and Levenshtein powers "how similar" — two answers to two different questions, computed with nearly the same machinery.

Where Levenshtein Distance Is Used

• Spell-checkers and autocorrect — suggest the dictionary word with the smallest edit distance from your typo.
• Fuzzy search and "did you mean?" — match queries to results even with typos.
• Deduplication and record matching — spot that "Jon Smith" and "John Smith" are almost certainly the same person.
• Bioinformatics — measure how similar two DNA or protein sequences are.
• Plagiarism and similarity detection — quantify how close two pieces of text are.

In each case, the raw distance is often turned into a similarity percentage so it is easier to read — for example, 1 − (distance / length of the longer string). A small distance means the strings are nearly identical; a large one means they are far apart.

Levenshtein and Text Comparison

When you compare text online, the tool is answering a related question: not just how far apart two texts are, but exactly where they differ. For showing the precise added and removed pieces, diff tools lean on LCS and the efficient Myers algorithm, while edit distance is the natural choice when you want a single similarity number. Understanding Levenshtein makes both the "how similar" and the "what changed" sides of text comparison click into place.

Frequently Asked Questions

What is the Levenshtein distance in simple terms?

It is the minimum number of single-character insertions, deletions, or substitutions needed to change one string into another. For "kitten" and "sitting" it is 3, because it takes two substitutions and one insertion.

Why is the Levenshtein distance of kitten and sitting 3?

Because the cheapest way to transform one into the other is three edits: substitute k with s, substitute e with i, and insert g at the end. No shorter sequence of edits exists.

What is the difference between Levenshtein distance and edit distance?

They usually mean the same thing. "Edit distance" is the general term; Levenshtein distance is the most common version, the one that allows insertions, deletions, and substitutions each costing 1. Other variants (like Damerau-Levenshtein) also count transpositions.

What is the time complexity of the Levenshtein algorithm?

The dynamic-programming solution runs in O(m × n) time for strings of length m and n. It uses O(m × n) space for the full matrix, or O(min(m, n)) if you only need the distance and not the list of edits.

How is Levenshtein distance different from LCS?

LCS measures what two strings share (the longest common in-order run) and drives diff tools. Levenshtein measures how far apart they are (the fewest edits) and drives similarity and fuzzy matching. Both use similar dynamic-programming grids.

How do you turn edit distance into a similarity score?

A common formula is 1 − (distance / length of the longer string), giving a value from 0 to 1 (or a percentage). Identical strings score 1 (100%); completely different strings score near 0.