A strong answer
The standard table, where dp[i][j] is the distance between the first i characters of one string and the first j of the other, costs O(m × n) time and space. For two 100,000-character strings that is ten billion cells, around 40 GB.
If only the distance is needed, each row depends only on the previous one, so two rows suffice: O(n) memory, about 800 KB here, with the same time. If the edits themselves are needed, Hirschberg's algorithm recovers them in O(m + n) memory: run the two-row DP forward over the first half of one string and backward over the second half, combine the two middle rows to find where an optimal path crosses the middle, then recurse on the two halves. It roughly doubles the time but keeps memory linear.
Time is often the bigger problem. If the strings are similar, or I only need to know whether the distance is at most k, I compute only a band of width 2k + 1 around the diagonal, since any cell farther away has distance above k: O(k × n). Doubling k until the answer fits gives O(d × n) for a true distance d. Myers-style algorithms exploit the same structure. For huge inputs on modern hardware, the anti-diagonals of the table are independent and can be computed in parallel or with vector instructions, and bit-parallel algorithms pack many cells into machine words.
What the interviewer is listening for
- Quantifying the table's size and recognizing it won't fit.
- Two-row space reduction, and why it loses the edits.
- Hirschberg for linear-space reconstruction.
- Banded or diagonal approaches when the distance is small.
Common mistakes
- Proposing the full table without checking its size.
- Assuming two rows are enough to print the edits.
- Ignoring that similar inputs allow much faster algorithms.