The LCS table uses space. Can we do better if we only need the length? Yes! Each row only depends on the previous row. Keep two rows: and . Swap after each row. Space: by making the shorter string the column dimension. Tradeoff: we lose reconstruction.
To reconstruct with space, use Hirschberg's algorithm (divide and conquer on the strings). Hirschberg combines divide-and-conquer with the space reduction to get both space and reconstruction.