Is the Edit Distance Within k
Print yes if the two strings can be made equal with at most k single-character edits,
where an edit is an insertion, a deletion, or a replacement.
kitten, sitting, k = 3 -> yes the distance is exactly 3
kitten, sitting, k = 2 -> no
abc, abd, k = 0 -> no
## Why the full table is too large
Problem #506 computes the exact distance in O(n m) time. Here the strings reach
2 * 10^4 characters, so the full grid is 4 * 10^8 cells.
But k is at most 100, and that changes what has to be computed.
## Only a band matters
Each edit changes the difference between the two consumed lengths by at most 1. So a path
using at most k edits can never stray more than k away from the diagonal:
any cell (i, j) on such a path has |i - j| <= k
Everything outside that band is irrelevant, because reaching it already costs more than
k. So compute only 2k + 1 cells per row, and the cost drops from O(n m) to
O(n k), which here is 2 * 10^6.
Restricting a table to the region the answer can reach is the general technique, and it applies whenever the question is "is the optimum within a bound" rather than "what is the optimum".
## Indexing by the offset
The clean formulation reindexes by d = j - i, running over -k .. k:
f[i][d] = the edit distance between the first i of a and the first i+d of b
The three transitions rewrite as
replace or match f[i-1][d] both indices advance, d unchanged
delete from a f[i-1][d+1] i advances, j does not, so d falls
insert into a f[i][d-1] j advances, i does not, so d falls
Iterate d ascending so f[i][d-1] is already available in the current row. Working out
those three offsets from the original recurrence is the exercise; guessing them produces
something that is right on the diagonal and wrong at the band edges.
## The immediate rejection
If |n - m| > k the answer is no before anything is computed, because the lengths alone
already differ by more than k edits can fix. That is also what keeps the band well
defined: d = m - n has to lie inside it for the final cell to exist.
a against abcd with k = 2 answers no for exactly this reason, and with k = 3
answers yes.
## Boundaries
abc against abc with k = 0 answers yes, and abc against abd with k = 0
answers no and with k = 1 answers yes. The pair pins down that k = 0 means exact
equality.
intention against execution with k = 5 answers yes, the distance being exactly 5,
so the comparison is at most rather than less than.
## Cost
Time O(n k). Space O(k) with two rows of the band.