Refactoring: LCS Space Optimization

LCS with a full 2D table uses O(N×M) memory. But dp[i][*] only depends on dp[i-1][*] and dp[i][*-1]. By keeping just two rows, we drop to O(min(N,M)) without changing time complexity.

Before: Full 2D Table

C++ — O(N×M) memory

vector> dp(n + 1, vector(m + 1, 0));
// N=5000, M=5000:  ~100 MB  (may exceed memory limit)

After: Two-Row Rolling

C++ — O(M) memory (two rows)

int lcs_optimized(string& s, string& t) {
    int n = s.size(), m = t.size();
    vector prev(m + 1, 0), curr(m + 1, 0);

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (s[i - 1] == t[j - 1])
                curr[j] = 1 + prev[j - 1];
            else
                curr[j] = max(prev[j], curr[j - 1]);
        }
        swap(prev, curr);
    }
    return prev[m];
}

// N=5000, M=5000:  ~40 KB  (100 MB → 40 KB!)

Rust — O(M) memory (two rows)

fn lcs_optimized(s: &str, t: &str) -> usize {
    let (n, m) = (s.len(), t.len());
    let s = s.as_bytes();
    let t = t.as_bytes();
    let mut prev = vec![0; m + 1];
    let mut curr = vec![0; m + 1];

    for i in 1..=n {
        for j in 1..=m {
            curr[j] = if s[i - 1] == t[j - 1] {
                1 + prev[j - 1]
            } else {
                prev[j].max(curr[j - 1])
            };
        }
        std::mem::swap(&mut prev, &mut curr);
    }
    prev[m]
}

💡 Always minimise memory when practical

Many contest problems have memory limits of 64–256 MB. A 5000×5000 int table is ~100 MB — dangerously close. The two-row version is ~40 KB. The pattern generalises: if dp[i] depends only on dp[i-1], you can roll.

Key Takeaways