Edit distance between strings of length m and n runs in O(mn) time and O(mn) space if you keep the full table. Give an algorithm that recovers the optimal alignment itself in O(min(m,n)) space, state its time complexity and explain the recursion.

Edit distance between strings of length m and n runs in O(mn) time and O(mn) space if you keep the full table. Give an algorithm that recovers the optimal alignment itself in O(min(m,n)) space, state its time complexity and explain the recursion.

Approach: Two rows suffice for the distance alone. To get the alignment, split one string in half and use forward and backward row scans to find where the optimal alignment crosses the midpoint.

Hirschberg's algorithm gives the alignment in O(mn) time and O(min(m,n)) space. Computing the distance alone needs only two rows, since row i depends on row i - 1, which is where the space bound starts, and the missing piece is the traceback. The divide and conquer step splits the first string at its midpoint i = m/2. Compute the last row of the forward table from the prefix of length i, and the last row of the backward table from the reversed suffix, each in linear space. The optimal alignment crosses column j where the sum of the two rows is minimised, which splits the problem into aligning the first i characters against the first j and the rest against the rest. Recurse on both halves. The work halves the first string at every level while the second string is split between the two calls, so the total work satisfies T(m,n) = mn + T(m/2, j) + T(m/2, n - j), which sums to at most 2mn, so the time is still O(mn) with a constant factor of about two. Only O(n) rows are live at any point because the recursion stack holds indices rather than tables.

Follow-up: How does the same divide and conquer idea apply to the longest common subsequence with arbitrary gap penalties?

Key concepts: hirschberg, divide and conquer, two rows, crossing point.