Coding Interview: How Do You Calculate Edit Distance with Dynamic Programming?

Problem and applicable scenarios

Given two strings source and target, return the minimum number of edits needed to transform source into target. One edit inserts one character, deletes one character, or replaces one character. Every operation costs one. Either string may be empty, and both contain only lowercase English letters.

source = "horse"
target = "ros"

horse -> rorse   replace h with r
rorse -> rose    delete r
rose  -> ros     delete e

answer = 3

Let m = source.length and n = target.length, with both lengths at most 2,000. The task asks only for the minimum cost, not an edit script. The Wagner–Fischer paper defines string correction as a minimum-cost sequence of insertions, deletions, and substitutions and gives an algorithm whose time is proportional to the product of the two lengths. Current 2026 interview guides still use edit distance as a canonical two-string dynamic programming exercise. This supports the topic's preparation value; it does not prove a particular company's frequency or attribution.

This problem appears in spell checking, fuzzy matching, record linkage, and sequence comparison, but production definitions may use weighted operations, transpositions, normalization, or domain-specific tokens. The interview version deliberately fixes unit-cost character edits so its state and proof are unambiguous.

What the interviewer evaluates

The first signal is a state definition with exact boundaries. Define dp[i][j] as the minimum edits needed to turn the first i characters of source into the first j characters of target. “The answer up to i and j” is too vague to justify a transition or initialize an empty prefix.

The second signal is deriving all three mismatching-character transitions. The final operation of an optimal solution must be one of delete, insert, or replace. Removing that final operation leaves a smaller prefix problem. The candidate must map each operation to the correct neighboring cell instead of memorizing three coordinates.

The third signal is handling matching final characters without inventing work. If source[i - 1] equals target[j - 1], an optimal solution can leave that character unchanged, so the value comes from dp[i - 1][j - 1]. The proof must also show that no cheaper solution is hidden by this choice.

The fourth signal is recognizing the dependency shape. A row uses only the previous row and its own left cell, so the full O(mn) matrix is unnecessary when only the distance is returned. Putting the shorter string on the column dimension gives O(min(m, n)) auxiliary space.

The final signal is preserving the problem contract. Swapping row and column strings is valid here because unit-cost insertion and deletion make the distance symmetric. It is not automatically valid when insertion and deletion have different weights. Unicode text also requires an explicit choice between UTF-16 code units, Unicode code points, and user-perceived grapheme clusters.

Questions to clarify before answering

• Which operations are allowed? This problem allows insertion, deletion, and replacement. Adjacent

transposition is not one operation.

• What does one edit cost? Every allowed operation costs one. Weighted costs change the recurrence and may

remove symmetry.

• What is the comparison unit? The prompt uses lowercase English letters, so JavaScript indexing is safe for

this implementation. General Unicode text needs a separate contract.

• Do we return only the distance or an edit script? Only the distance. Reconstructing operations normally

retains the full table or explicit predecessor information.

• May either input be empty? Yes. Transforming an empty string into a prefix of length j needs exactly j

insertions; the reverse needs i deletions.

• What are the size limits? Lengths up to 2,000 make O(mn) time acceptable but make exponential recursion

and unnecessary full-table memory undesirable.

• Can the inputs be swapped to save memory? Yes under this unit-cost contract because the distance is

symmetric. State that assumption before using it.

30-second answer framework

“I define dp[i][j] as the minimum edits from the first i source characters to the first j target characters. Empty-prefix costs initialize the first row and column. Equal final characters use the diagonal unchanged. Otherwise the last edit is delete, insert, or replace, so I take one plus the minimum of the cell above, left, and diagonal. Each cell depends only on the previous row and the current row's left value, so I put the shorter string on the columns and keep two rows. That gives O(mn) time and O(min(m, n)) space. I verify empty strings, equal strings, asymmetric lengths, and the result against a full-table reference on small inputs.”

Step-by-step deep solution

Start from prefixes. Let dp[i][j] be the minimum number of allowed edits that transforms source[0..i - 1] into target[0..j - 1].

The empty-prefix boundaries follow directly from the contract:

dp[0][j] = j   // insert all j target characters
dp[i][0] = i   // delete all i source characters

For nonempty prefixes, inspect their final characters. If they match, keeping that shared final character reduces the problem to the two shorter prefixes:

if source[i - 1] == target[j - 1]:
  dp[i][j] = dp[i - 1][j - 1]

If they differ, classify the final edit of any optimal sequence:

delete source[i - 1]:       dp[i - 1][j]     + 1
insert target[j - 1]:       dp[i][j - 1]     + 1
replace the final character: dp[i - 1][j - 1] + 1

dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])

These are exhaustive because the last operation must be one of the three allowed edits. They are constructive: append the named edit to an optimal solution for the selected smaller prefix, and it produces a legal solution for (i, j). Conversely, remove the last edit from any optimal solution; the remainder solves the corresponding smaller prefix, so it cannot cost less than that cell. This proves the mismatch recurrence.

For matching final characters, there is an optimal solution that leaves them matched. If some optimal sequence edits the final source or target character, remove those final effects and align the equal characters instead; this does not increase the cost. The remaining work is exactly the diagonal prefix problem. Induction on i + j, anchored by the empty-prefix boundaries, proves every cell and therefore dp[m][n].

Only three earlier values are needed while filling a row: previous[j] for deletion, current[j - 1] for insertion, and previous[j - 1] for replacement or a match. The code makes the shorter string the columns. That swap is a memory optimization under this symmetric unit-cost definition; it does not change the answer.

export function editDistance(source: string, target: string): number {
  const rows = source.length >= target.length ? source : target
  const columns = source.length >= target.length ? target : source

  let previous = Array.from(
    { length: columns.length + 1 },
    (_, index) => index,
  )

  for (let row = 1; row <= rows.length; row += 1) {
    const current = new Array<number>(columns.length + 1)
    current[0] = row

    for (let column = 1; column <= columns.length; column += 1) {
      if (rows[row - 1] === columns[column - 1]) {
        current[column] = previous[column - 1]
        continue
      }

      const deleteCost = previous[column] + 1
      const insertCost = current[column - 1] + 1
      const replaceCost = previous[column - 1] + 1
      current[column] = Math.min(deleteCost, insertCost, replaceCost)
    }

    previous = current
  }

  return previous[columns.length]
}

For source = "horse" and target = "ros", the shorter column dimension has length three. The final row ends in three, matching the replacement-plus-two-deletions sequence. The algorithm returns the cost; it does not claim that this particular edit sequence is unique.

Complexity, boundaries, and engineering choices

The algorithm fills (m + 1)(n + 1) conceptual states, so time is O(mn). Each row has min(m, n) + 1 entries, and only two rows exist at once, so auxiliary space is O(min(m, n)). Reallocating one row per iteration does not change the bound; two reusable arrays can reduce allocation pressure without changing the algorithm.

The maximum answer under unit insertion, deletion, and replacement is max(m, n): replace the first min(m, n) characters, then insert or delete the length difference. The minimum is at least |m - n|, because each edit changes length by at most one. These bounds are useful assertions in tests.

For general JavaScript strings, indexing operates on UTF-16 code units. String iteration preserves surrogate pairs by yielding Unicode code points, but it can still split one grapheme cluster such as an emoji plus a skin tone or a zero-width-joiner sequence. A production similarity feature must decide whether edits apply to code units, code points, normalized grapheme clusters, words, or domain tokens before choosing a tokenizer. Silent normalization can also change product semantics, so it belongs in the contract rather than inside this DP loop.

If the caller asks only whether distance is at most k, first reject when |m - n| > k, then evaluate only a diagonal band and stop when no state in the active band can remain within k. That is a different output contract; the full-distance implementation should not add that complexity speculatively.

High-quality sample answer

“I would model the problem over prefixes. Let dp[i][j] be the minimum cost to turn the first i source characters into the first j target characters. The empty-prefix boundaries are their lengths. For equal final characters I keep the diagonal value. For different final characters, I classify an optimal sequence by its last edit: deleting uses the cell above, inserting uses the cell to the left, and replacing uses the diagonal, with one added to the minimum. Those cases are exhaustive, and removing the last edit proves the recurrence in the other direction.

“Since a cell uses only the previous row and the current row's left cell, I keep two rows. Unit insertion and deletion costs make this distance symmetric, so the shorter string can be the columns and memory becomes O(min(m, n)); time remains O(mn). I would not use that swap for asymmetric weights. I would test both empty directions, equal strings, the horse to ros example, and short generated strings against a full-table version. If the interviewer needs the edit script, I would retain predecessor information instead of promising to recover it from overwritten rows.”

Common mistakes

• Using greedy character matching → repeated characters and later shifts make a locally convenient edit lose

the global minimum → define optimal prefix states and compare all legal final operations.

• Initializing the first row and column to zero → empty-string cases become free → **set boundary costs to

their prefix lengths.**

• Mixing up insert and delete neighbors → the code may pass symmetric examples while failing asymmetric

prefixes → explain what string remains after removing the final operation.

• Adding one when final characters match → unchanged equal characters are charged as replacements → **copy

the diagonal exactly on a match.**

• Returning a rolling-row answer while promising an edit script → overwritten predecessors cannot reconstruct

the path → retain the matrix or backpointers when operations are required.

• Swapping strings under asymmetric weights → insertions in one direction become deletions in the other →

keep the original orientation unless the cost model is symmetric.

• Calling JavaScript indices “characters” for arbitrary Unicode → surrogate pairs or grapheme clusters get

counted unexpectedly → define and tokenize the comparison unit explicitly.

A focused test set includes ("", "") = 0, ("", "abc") = 3, ("abc", "") = 3, ("same", "same") = 0, ("aaaa", "aa") = 2, ("horse", "ros") = 3, and ("intention", "execution") = 5. Compare the rolling implementation with a full-table reference over all short strings from a tiny alphabet. Also check identity, symmetry under this cost model, |m - n| ≤ d ≤ max(m, n), and the triangle inequality on generated triples. Finally, run length-2,000 equal and fully different inputs to confirm the extreme-size path stays within the expected quadratic time and linear space.

Interview follow-ups

Follow-up 1: How would you return the actual edit operations?

Keep the full table and backtrack from (m, n). A match moves diagonally without emitting an operation; otherwise choose a neighboring cell whose value plus the corresponding edit cost equals the current value. Define a stable tie-break rule because multiple minimum scripts may exist. The straightforward method uses O(mn) space. A linear-space reconstruction is possible with divide-and-conquer techniques, but it is a separate algorithm and should be introduced only when the memory requirement demands it.

Follow-up 2: What changes when operations have different weights?

Add the relevant weight to each transition instead of one. The same optimal-substructure proof works when costs are nonnegative and defined by the contract. If insertion and deletion costs differ, distance may be directional, so swapping the strings to shorten the row is no longer automatically correct. Negative edit costs break the usual interpretation and require reconsidering the model.

Follow-up 3: How would you support adjacent transposition?

First clarify whether a transposition swaps only adjacent characters and whether overlapping transpositions are allowed. A restricted optimal-string-alignment recurrence can inspect two additional preceding characters and a cell two rows and columns back. Full Damerau–Levenshtein distance has different state requirements. Merely adding one informal diagonal check can implement the wrong variant.

Follow-up 4: What is the relation to longest common subsequence?

If replacement is forbidden or costs the same as one deletion plus one insertion, an insertion-and-deletion distance can be derived from LCS as m + n - 2 * LCS(source, target). With unit-cost replacement, that formula is not generally the edit distance: replacing one mismatching character costs one, while delete-plus-insert costs two. State the operation costs before using the relationship.

Follow-up 5: How would you answer “is the distance at most k?” faster?

Return false immediately when the length difference exceeds k. Otherwise compute only states within k of the main diagonal, treating cells outside the band as unreachable, and stop if the active frontier cannot get back within the budget. This can reduce work substantially when k is small, while the worst case for unrestricted distance remains quadratic.

Follow-up 6: How would you handle real user-visible Unicode text?

Choose the unit with the product owner. Code-point iteration prevents splitting surrogate pairs, but it still splits some user-perceived characters. Grapheme segmentation better matches visible characters, and Unicode normalization may make canonically equivalent sequences compare consistently. Locale, case folding, accents, and token-level rules are product decisions. Apply that preprocessing before DP and test examples from the supported languages.

Follow-up 7: Can one row replace two rows?

Yes. Before overwriting dp[j], save its old value as the next diagonal; dp[j] still represents the cell above, and dp[j - 1] already represents the current row's left cell. This reduces the constant factor, not the asymptotic space. In an interview, two rows are often easier to prove and less error-prone unless the interviewer specifically requests the in-place variant.