Levenshtein edit distance (string similarity)

Published: 2026-09-05

What Levenshtein distance measures (insert, delete, substitute), how the DP table works, UTF-16 caveats, and when raw edit count beats fuzzy “similarity” scores.

Levenshtein distance (also called edit distance) is the smallest number of single-character insertions, deletions, and substitutions needed to turn one string into another. It is a classic measure of how “close” two spellings are—typos, OCR noise, or near-duplicate IDs—without claiming a 0–1 “similarity percentage” unless you normalize it yourself.

LocalTools’ Levenshtein distance tool computes that integer (and optionally shows the dynamic-programming matrix) entirely in your browser. Your strings never leave the tab—same local-only model as other paste tools.

The three edits (each cost 1)

Given string A and string B, every step is one of:

Operation	Effect	Cost
Insert	Add one character into A’s path toward B	1
Delete	Remove one character	1
Substitute	Replace one character with a different one	1

Matching characters cost 0. The distance is the minimum total cost over all sequences of edits—not a count of how many characters differ in place (that would ignore insertions/deletions).

Classic textbook example:

kitten → sitting
Distance 3: substitute k→s, substitute e→i, insert g

Identical strings have distance 0. An empty string vs a string of length n has distance n (all inserts or all deletes).

Distance is not a similarity score

Levenshtein returns a non‑negative integer. Longer pairs can share a large absolute distance even when they “feel” related, and short pairs look “far” after one typo (ab vs ac is already 1).

People often want a normalized score such as:

similarity ≈ 1 − (distance / max(length(A), length(B)))

That is useful for thresholds (“keep if similarity ≥ 0.9”), but it is not what the classic algorithm outputs, and LocalTools intentionally shows the raw distance. For very long texts, prefer chunked comparisons or specialized fuzzy matchers in your codebase rather than one giant edit-distance call.

How the DP table works (intuition)

The standard algorithm fills a table dp[i][j] = distance between the first i characters of A and the first j of B:

First row/column: empty prefix costs the other length (all inserts or deletes).
Each cell takes the minimum of: delete (dp[i−1][j] + 1), insert (dp[i][j−1] + 1), or substitute/match (dp[i−1][j−1] + cost).

The answer is the bottom-right cell. For teaching and debugging short strings, seeing the full matrix helps; for long inputs, implementations keep only two rows of the table so memory stays linear in one string’s length.

On LocalTools, Show DP matrix is available only when both strings are short enough to render comfortably; the numeric distance still uses the full inputs (up to the page’s safe length cap).

What “character” means here (UTF-16)

JavaScript strings are indexed in UTF-16 code units. The tool compares those units (same idea as charCodeAt), so:

Most Latin letters and digits are one unit each.
Many emoji and some symbols are two code units (a surrogate pair). Editing one visible glyph can cost 2 in Levenshtein terms if you think in “user-perceived characters.”

If you need grapheme-aware distance, you need a different pipeline (normalize to grapheme clusters first). For IDs, emails, and ASCII-ish product codes, UTF-16 Levenshtein is usually what libraries and interview questions mean.

When edit distance helps—and when it does not

Good fits

Spotting typos between two known candidates (color vs colour is distance 1 or 2 depending on spelling).
Teaching / debugging fuzzy-match thresholds before you wire them into search.
Comparing short labels, SKUs, or filenames where a few edits matter.

Poor fits

Exact uniqueness of lines: use Dedupe lines—equality, not edit distance.
Reviewing large text changes: use a unified diff / text diffs workflow; Levenshtein does not show where lines moved.
Bulk rewrite of many occurrences: Find & replace (batch) or regex testing.
Semantic similarity (“these sentences mean the same thing”)—that needs embeddings or NLP, not character edits.

Near-duplicates in a long list are still often handled by normalize → sort/dedupe first (sorting and deduping, whitespace), then Levenshtein only on suspicious pairs.

Practical workflow

Paste the two strings you want to compare (or use the kitten / sitting example).
Read the Levenshtein distance—lower means fewer single-unit edits.
Optionally enable Show DP matrix on short strings to see how prefixes accumulate cost.
If either string is huge, trim to the relevant window; the page caps length so the tab stays responsive.
Decide your own threshold or normalization if you need a pass/fail “similar enough” rule in product code.

Why compute it locally

Fuzzy-match demos that upload both strings can see customer names, unreleased SKUs, or support paste. LocalTools runs the DP in your browser only—nothing is sent to LocalTools servers or third-party APIs for the comparison.

Try it locally

Open Levenshtein distance:

Enter String A and String B—the distance updates as you type.
Turn on Show DP matrix when both sides are short enough to explore the table.
Remember: the number is minimal edit cost, not a 0–1 similarity score.