526. 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.

Constraints - `1 ≤ length of a ≤ 20000` - `1 ≤ length of b ≤ 20000` - `0 ≤ k ≤ 100` - both strings contain only lowercase letters