The site's fourteenth approximate match entry, and a direct answer to the forward reference Damerau–Levenshtein Distance's own Complexity section left open: "the true unrestricted algorithm... needs an additional small table indexed by alphabet character and is not implemented on this page." That sibling page ships OSA (Optimal String Alignment) distance — a fourth edit type, adjacent transposition, bolted onto plain edit distance with one constant-time check per cell, but with a rule attached: once a pair of characters has been swapped, neither one may be touched again. The true Damerau–Levenshtein distance drops that rule. It's named for Robert Lowrance and Yehoshua Wagner's 1975 paper formalizing a correct algorithm for the distance Fred Damerau's 1964 study actually defined — OSA, despite being the version nearly everyone ships, is a deliberately cheaper approximation to it, not the same number. This page is that algorithm: the same CA → ABC pair that sibling page's Pitfalls section already uses to show the two distances disagree (true = 2, OSA = 3) is the live demo below, toggling between both on one table.
Fixed pair A = "CA", B = "ABC" — the exact pair
Damerau–Levenshtein Distance's own Pitfalls
section uses to show the two distances disagree. Press Step or Run
to fill the table in True (unrestricted) mode: watch dp[2][3] reach all
the way back to dp[0][0] — not just two rows/columns, however far the matching last-seen
positions happen to be — settling the distance at 2 (transpose CA→AC,
insert B between them). Switch the mode dropdown to OSA (restricted) and
rerun on the identical pair: that version can only ever look back exactly two rows and columns, so it
can't find the same route and the distance comes back 3 instead — same input, same
table shape, only how far back the transpose option is allowed to reach differs.
OSA's transposition check only ever looks at dp[i-2][j-2] — exactly two rows and
columns back, because it hardcodes the assumption that a swapped pair sits at A[i-2],A[i-1]
versus B[j-2],B[j-1] and nowhere else. The true algorithm replaces that fixed offset with
two lookups, updated as the table fills: i1, the most recent row where A held
the character B currently has at j-1; and j1, the most recent
column (within the current row) where B held the character A currently has at
i-1. When both exist, position i1 in A and position i
in A hold characters that are mirror-swapped with positions j1 and j
in B — exactly a transposed pair, however far apart they actually sit:
dp[i][j] = min(
dp[i-1][j-1] + (A[i-1] === B[j-1] ? 0 : 1), // match or substitute
dp[i-1][j] + 1, // delete A[i-1]
dp[i][j-1] + 1, // insert B[j-1]
dp[i1-1][j1-1] + (i-i1-1) + 1 + (j-j1-1) // transpose, when i1>0 and j1>0
)
The transpose option's cost has three parts: dp[i1-1][j1-1] for everything already
settled before either swapped character; (i-i1-1) deletions for any characters of
A sitting strictly between positions i1 and i; and
(j-j1-1) insertions for any characters of B sitting strictly between
j1 and j; plus 1 for the swap itself. On "CA"/
"ABC", the only matches are each string's own single character — C appears in
A at row 1 and is what B holds at column 3; A appears in
A at row 2 and is what B holds at column 1. At cell dp[2][3],
that gives i1=1, j1=1: zero deletions (i-i1-1 = 0, the two
positions are adjacent in A), one insertion (j-j1-1 = 1, for
B), plus the swap — dp[0][0] + 0 + 1 + 1 = 2. OSA's rule never considers this
at all: it can only look at dp[0][1] (two back from dp[2][3]), which isn't
the same base case.
The lookups above are kept in a plain object (da) mapping each character seen so far in
A to the row it last appeared in, refreshed after each row finishes, plus a per-row
db for the same idea along B. Two extra sentinel rows and columns, holding a
value (maxdist = m + n) larger than any real answer, let the i1-1/
j1-1 lookups stay in-bounds even before either character has been seen at all — the
standard Lowrance–Wagner formulation, rather than special-casing "no prior match yet" directly:
function trueDamerauLevenshtein(a, b) {
const m = a.length, n = b.length;
const maxdist = m + n;
const da = {}; // last row (1-indexed) each character of a/b was seen in A
// d is (m+2) x (n+2): index 0 and the final row/column are sentinels.
const d = Array.from({ length: m + 2 }, () => new Array(n + 2).fill(0));
d[0][0] = maxdist;
for (let i = 0; i <= m; i++) { d[i + 1][0] = maxdist; d[i + 1][1] = i; }
for (let j = 0; j <= n; j++) { d[0][j + 1] = maxdist; d[1][j + 1] = j; }
for (let i = 1; i <= m; i++) {
let db = 0;
for (let j = 1; j <= n; j++) {
const i1 = da[b[j - 1]] || 0;
const j1 = db;
let cost;
if (a[i - 1] === b[j - 1]) { cost = 0; db = j; }
else { cost = 1; }
d[i + 1][j + 1] = Math.min(
d[i][j] + cost, // match/substitute
d[i + 1][j] + 1, // delete
d[i][j + 1] + 1, // insert
d[i1][j1] + (i - i1 - 1) + 1 + (j - j1 - 1) // transpose
);
}
da[a[i - 1]] = i;
}
return d[m + 1][n + 1];
}
Verified against a brute-force search, not just asserted. "True" distance is defined
operationally — whatever a minimum-cost sequence of insert/delete/substitute/adjacent-swap operations
achieves — so it needs an independent ground truth to check against, not just internal consistency.
A brute-force breadth-first search over the literal operation graph (every single-character
insert/delete/substitute, every adjacent swap, on the actual current string, no shortcuts) was run
against the algorithm above across all 14,641 string pairs up to length 4 on a 3-letter alphabet:
zero mismatches. A second, independent check reconstructed the actual edit script via
backtracking (not just the cost) and replayed it character-by-character against the original string,
confirming it both produces B exactly and costs exactly the number of edits the table
claims — across 150,000 random pairs (lengths up to 11, alphabets of four and five letters): again
zero mismatches.
The transposed pair doesn't have to be adjacent in the original string — and that can look
like the algorithm is giving a transposition away for free. On "CA"/"ABC"
the swapped characters (C and A) happen to sit right next to each other, since
that's the whole of A. In general, i1 and i can be many rows
apart, with real characters of A in between — those are charged as ordinary deletions
(i-i1-1 of them), and the corresponding gap in B as ordinary insertions
(j-j1-1 of them), both folded into the same +1-for-the-swap cost alongside
them. Nothing is free: the formula's total is exactly what a literal "delete the characters in between,
swap the now-adjacent pair, insert B's in-between characters" sequence would cost if done
as separate explicit edits — checked directly by the backtracking-and-replay verification above, which
exercises exactly this shape whenever a random pair happens to produce a non-adjacent transpose.
Unlike OSA, this table can't be shrunk to a rolling window.
OSA's own Complexity section notes its
table only ever reads two rows back, so a rolling three-row window would hold the distance alone without
keeping the whole table. That trick doesn't carry over here: i1 can point at any
earlier row, not a fixed offset, so a cell computed early in the fill can still be read from a cell
computed near the very end. The full O(m·n) table has to stay resident for the whole
computation — one real cost of the extra correctness, not just the small constant-size da/
db bookkeeping.
Time: O(m·n) — identical to OSA's. Each cell does the same constant
number of comparisons; the da/db lookups are a plain object/map access, still
O(1) amortized per cell (or O(1) worst case with a fixed-size array when the
alphabet is known and bounded, e.g. ASCII). Space: O(m·n) for the table
(see Pitfalls for why it can't be reduced the way OSA's can), plus O(σ) for the
alphabet-indexed da table, where σ is the number of distinct characters
actually appearing across both strings — negligible next to the table itself for any realistic
alphabet.
OSA remains the right default for spell-checkers and fuzzy autocomplete — cheaper to reason about,
and the gap from the true distance only opens on the specific shape this page's example shows (an
insertion or deletion landing on a character that was just part of a transposition), rare enough in
real typing mistakes that most libraries never notice. Reach for the true distance instead when an
algorithm downstream actually needs a real metric — BK-Tree
is exactly that case, since its pruning correctness depends on the triangle inequality holding, which
OSA provably violates on this same
CA/AC/ABC triple. For the full picture across all fourteen
approximate-match entries, see
Choosing an Approximate String Matcher.