Longest Common Subsequence and Levenshtein Edit Distance: 2D Grid DP & Space Reductions

String comparison algorithms form the backbone of bioinformatics sequence alignment, git diff utilities, and automated spell-checkers. Both Longest Common Subsequence (LCS) and Edit Distance share a canonical 2D grid dynamic programming structure.

1. Longest Common Subsequence (LCS)

Given two strings $S_1$ of length $M$ and $S_2$ of length $N$, find the length of the longest subsequence present in both strings.

Mathematical Recurrence

if (S1[i - 1] == S2[j - 1]) {
    dp[i][j] = 1 + dp[i - 1][j - 1];
} else {
    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}

2. Levenshtein Edit Distance

Determine the minimum number of character operations (insert, delete, substitute) required to transform string $S_1$ into string $S_2$.

// Edit Distance State Transition
if (S1[i - 1] == S2[j - 1]) {
    dp[i][j] = dp[i - 1][j - 1]; // No cost match
} else {
    dp[i][j] = 1 + min({
        dp[i - 1][j],    // Deletion from S1
        dp[i][j - 1],    // Insertion into S1
        dp[i - 1][j - 1] // Substitution
    });
}

3. Linear Space Optimization

Since each cell dp[i][j] depends only on the current row and the previous row, we can reduce the memory requirement from $O(M cdot N)$ to $O(min(M, N))$ by maintaining two 1D vectors.