Cairn
algorithms · approximate match · O(m·n) time, O(m·n) space

↩ back to Approximate Match

True Damerau–Levenshtein Distance (Lowrance–Wagner Algorithm)

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.

Try it

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.

step 0
Press Step or Run.

Why it works

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.

Reference implementation

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];
}

Pitfalls

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.

Complexity

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.