Challenge: LCS Space Optimization

The LCS table uses $O(mn)$ space. Can we do better if we only need the length? Yes! Each row only depends on the previous row. Keep two rows: $prev$ and $curr$. Swap after each row. Space: $O(\min(m, n))$ by making the shorter string the column dimension. Tradeoff: we lose reconstruction.

To reconstruct with $O(n)$ space, use Hirschberg's algorithm (divide and conquer on the strings). Hirschberg combines divide-and-conquer with the space reduction to get both $O(n)$ space and reconstruction.