Longest Common Subsequence

LCS finds the longest sequence of characters that appears in the same order in two strings (not necessarily contiguous). It's the foundation of diff tools, version control, and DNA sequence alignment.

The Recurrence

Let dp[i][j] = LCS of prefixes s[0..i) and t[0..j).

// If characters match, extend the LCS:
if s[i-1] == t[j-1]:
    dp[i][j] = 1 + dp[i-1][j-1]
// Otherwise, take the best of skipping either character:
else:
    dp[i][j] = max(dp[i-1][j], dp[i][j-1])

C++ — LCS

int lcs(string& s, string& t) {
    int n = s.size(), m = t.size();
    vector> dp(n + 1, vector(m + 1, 0));

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

Rust — LCS

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

    for i in 1..=n {
        for j in 1..=m {
            if s[i - 1] == t[j - 1] {
                dp[i][j] = 1 + dp[i - 1][j - 1];
            } else {
                dp[i][j] = dp[i - 1][j].max(dp[i][j - 1]);
            }
        }
    }
    dp[n][m]
}

Key Takeaways

→ LCS: 2D DP comparing prefixes — match extends, mismatch skips.
→ O(N×M) time, O(N×M) memory. Space can be reduced to O(min(N,M)).
→ Reconstruct the actual subsequence by tracing back through the table.

The Recurrence

C++ — LCS

Rust — LCS

Key Takeaways

Practice