LCS (Longest Common Subsequence)

Concept

Classic DP comparing two strings/arrays. Build a 2D table where dp[i][j] = LCS length of first i chars and first j chars. If characters match, dp[i][j] = dp[i-1][j-1] + 1. Otherwise, dp[i][j] = max(dp[i-1][j], dp[i][j-1]).

When to Use

• ▸Finding longest common subsequence of two strings
• ▸Diff tools (comparing two files/texts)
• ▸DNA sequence alignment
• ▸Measuring string similarity

Intuition

Compare characters one by one. If they match, both contribute to the subsequence. If not, try skipping one from each string and take the better result. The table builds up all subproblem answers. Each cell asks: what's the best LCS we can get using the first i characters of string A and first j characters of string B?

Complexity

Template Code

#include<bits/stdc++.h>
using namespace std;

int main(){
    ios_base::sync_with_stdio(0), cin.tie(0);

    string a, b;
    cin >> a >> b;

    int n = a.size(), m = b.size();
    vector<vector<int>> dp(n+1, vector<int>(m+1, 0));

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

    cout << dp[n][m] << "\n";

    return 0;
}

// Sample Input:
// abcde
// ace
//
// Sample Output:
// 3