Edit Distance's table fills all
(m+1)(n+1) cells to answer "what's the fewest edits, whatever that number turns out to
be?" Often the real question is narrower: "is it within k edits?" — a spell
checker doesn't care that two words are 40 edits apart, only that they aren't within 2.
Ukkonen's observation: cell dp[i][j] can only ever be reached by at
least |i − j| inserts or deletes, just to close the length gap between a prefix of
length i and one of length j — so any cell with |i − j| > k
is guaranteed to hold a value greater than k before a single comparison runs. Skip
those cells entirely, compute only the diagonal band |i − j| ≤ k, and the answer comes
out identical whenever k is large enough — for a fraction of the work.
Same pair Edit Distance uses, so the answer is
already known: A = "kitten", B = "sitting", true distance 3.
Pick a band width k and press Step or Run — cells
inside the band fill in exactly as they would in the full table; cells outside it are never touched by
a correct implementation, shown dim. At k = 0 the band can't even reach the bottom-right
corner (the strings differ in length by 1, more than 0), and a correct implementation has to say so
rather than guess. At k = 1, the band is already wide enough to find the true distance
of 3 while computing just 20 of the full table's 56 cells — check the stats line.
Switch sentinel to buggy (0 default, no ∞) to run the broken
variant Pitfalls describes, live: instead of treating an out-of-band or not-yet-computed cell as
"infinitely far" (so it's correctly ignored by the surrounding min), this variant reads
it straight off a plain array that JavaScript defaults to 0. Watch the out-of-band cells
now render as 0 instead of dim — and watch the final answer quietly shrink to match
k instead of reporting the true distance, or "impossible," for every k below
3.
The band bound is a lower bound on path length, not a heuristic guess. Any way of turning the
first i characters of A into the first j characters of
B has to account for a length difference of |i − j| somehow — every
substitution and every match leaves the length gap unchanged, only insert and delete move it, one
character at a time. So reaching dp[i][j] at all costs at least |i − j|
edits, regardless of what the two prefixes actually contain. If a k-edit budget is all
that's being asked about, any cell with |i − j| > k is provably irrelevant before its
characters are even compared — this is the same bound
Bitap with Edit Distance enforces a
different way, by only ever tracking k+1 error levels in a bit-parallel word instead of
restricting which table cells exist.
The recurrence inside the band is unchanged from Edit Distance's own three-way
minimum — match for free, or pay one edit for the cheapest of substitute, delete, insert. What
changes is what a lookup means when it lands on a neighbor outside the band: a cell at the
band's own edge (|i − j| = k) has a neighbor one step further off the diagonal
(|i − j| = k+1), which was never computed because it can't matter — reaching it would
already cost more than k. Treating that missing neighbor as infinitely expensive is what
correctly propagates "not reachable within budget" outward from the band's edge to the final answer.
Get that substitution wrong and the propagation breaks — see Pitfalls.
Only ever visits O(k) cells per row instead of O(n), and returns
Infinity — not a number — when k isn't big enough:
function bandedEditDistance(a, b, k) {
const m = a.length, n = b.length;
const inBand = (i, j) => Math.abs(i - j) <= k;
const written = new Set();
const dp = new Map();
const get = (i, j) => (inBand(i, j) && written.has(i + ',' + j)) ? dp.get(i + ',' + j) : Infinity;
for (let i = 0; i <= m; i++) {
const lo = Math.max(0, i - k), hi = Math.min(n, i + k);
for (let j = lo; j <= hi; j++) {
let val;
if (i === 0 && j === 0) {
val = 0;
} else if (i > 0 && j > 0 && a[i - 1] === b[j - 1]) {
val = get(i - 1, j - 1);
} else {
const sub = (i > 0 && j > 0) ? get(i - 1, j - 1) + 1 : Infinity;
const del = i > 0 ? get(i - 1, j) + 1 : Infinity;
const ins = j > 0 ? get(i, j - 1) + 1 : Infinity;
val = Math.min(sub, del, ins);
}
dp.set(i + ',' + j, val);
written.add(i + ',' + j);
}
}
return get(m, n); // Infinity means "more than k edits apart"
}Skip the infinity sentinel and the algorithm doesn't crash — it lies, plausibly.
Build the same band from a plain Array(...).fill(0) table instead of a map guarded by
inBand, and every out-of-band or not-yet-written cell silently reads back
0 — "free," not "unreachable." Checked against the shipped page's own broken-sentinel
mode on "kitten"/"sitting" (true distance 3): at k = 0 the
correct version reports "impossible" (the length gap alone exceeds the budget), the buggy version
reports 0. At k = 1, correct reports 3 (the true
answer, already reachable at this band width); buggy reports 1. At k = 2,
correct still reports 3; buggy reports 2. The pattern is exact and easy to miss in
production: the buggy version always reports min(k, true distance) — a number that looks
exactly like a legitimate answer, changes sensibly as k grows, and only stops being wrong
once k happens to reach the true distance. Nothing about the output looks broken; only
comparing it against the untouched full table (or, as here, against the correct-sentinel mode run on
the identical input) exposes it.
An off-by-one band width doesn't corrupt answers — it just quietly demands a bigger
k than it should. Define the band with a strict inequality,
|i − j| < k, instead of |i − j| ≤ k, and the sentinel logic above still
saves every genuinely out-of-band cell correctly — but the band itself is now one column narrower than
the budget promised. Checked in a scratch variant: on the same pair, the strict-inequality band needs
k = 2 to compute the same 20 cells and reach the same answer (3) that the correct
≤ band reaches at k = 1; at k = 1 the strict version reports
"impossible" even though a width-1 band is genuinely enough. No wrong finite numbers come out of this
version — only a budget that silently buys one less unit of slack than requested, a different failure
shape from the sentinel bug above (wrong answer vs. overly conservative "no").
The band only pays off when k stays small relative to the strings.
As k grows toward max(m, n), the band widens until it covers the whole
table and the savings vanish — try k = 4 above and watch the stats line close in on 56
of 56. This is the same trade Bitap with Edit Distance's Pitfalls
section makes from the opposite direction: both algorithms are only cheap because they assume the
answer, or the budget worth caring about, is small.
Time: O(k·min(m, n)) — each of roughly min(m, n) rows
computes at most 2k+1 cells, versus O(m·n) for the unrestricted table.
Space: O(k·min(m, n)) for the same reason, or O(k) if only
the two most recent diagonals are kept — the same rolling-row trick Edit Distance's own space-optimized mode uses on
the unrestricted table.
This only ever helps when the answer (or the threshold worth reporting) is known to be small —
exactly the assumption spell checkers, approximate diff, and DNA read alignment tools
make when they use a bounded edit distance instead of the full table. For a different way of exploiting
the same bound, packing the whole error budget into the bits of one machine word instead of restricting
which table cells exist, see Bitap with Edit
Distance (Wu–Manber). A sixth entry, Jaro-Winkler
Similarity, bounds a search window too — but around individual characters rather than table
cells, trading the exact edit count this page and its siblings compute for a cheaper similarity
score. For a side-by-side comparison across all eleven approximate-match entries, see Choosing an Approximate String Matcher.