Sequence DP — Longest Common Subsequence

Sequence DP Pattern

Two sequences compared with a 2D table. Each cell (i,j) represents the LCS of the first i chars of s1 and first j chars of s2. If chars match, extend the diagonal. If not, take the max of skipping either.

Recurrence

if s1[i-1] == s2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1 // match!
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])

Interactive Visualization

Computing

Match (diagonal)

Max of skip

S1:S2:

Step 0 of 0

Cell

—

Comparing

—

dp[i][j]

—

LCS Length

—

Ready. Press Play or Next to start.

✓ Done

Speed

C++ — LCS

int longestCommonSubsequence(string s1, string s2) {
    int m = s1.size(), n = s2.size();
    vector<vector<int>> dp(m+1, vector<int>(n+1, 0));

    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            if (s1[i-1] == s2[j-1])
                dp[i][j] = dp[i-1][j-1] + 1;
            else
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);

    return dp[m][n];
}

Complexity

Time

O(M × N)

M and N are string lengths.

Space

O(M × N)

Can optimize to O(min(M,N)).

📝 Notes

▼