DP lecture-25 Longest Common Subsequence (LCS) — Complete Notes

🔹 1. Definition

The Longest Common Subsequence (LCS) of two strings is the longest sequence that appears in both strings in the same order, but not necessarily contiguous.

👉 Example:

• s1 = "abcde"
• s2 = "ace"
• ✅ LCS = "ace" (length = 3)

---

🔹 2. Subsequence vs Substring

Type	Meaning
Subsequence	Can skip characters
Substring	Must be continuous

👉 Example:

• "ace" is subsequence of "abcde" ✅
• "aec" is NOT ❌ (order changed)

---

🔹 3. Recursive Thinking (Brute Force)

Case 1: Characters match

f(i, j) = 1 + f(i-1, j-1)

Case 2: Not match

f(i, j) = max(f(i-1, j), f(i, j-1))

Base Case

if i < 0 or j < 0 → return 0

---

🔹 4. DP Formulation (Tabulation)

Let:

dp[i][j] = LCS length of first i chars of s1 and first j chars of s2

---

🔹 5. Transition

• If match:

dp[i][j] = 1 + dp[i-1][j-1]

• If not match:

dp[i][j] = max(dp[i-1][j], dp[i][j-1])

---

🔹 6. Base Case

dp[0][j] = 0
dp[i][0] = 0

---

🔹 7. DP Table Visualization

For s1 = "abc" and s2 = "ac":

      ""  a  c
   ----------------
"" |  0  0  0
a  |  0  1  1
b  |  0  1  1
c  |  0  1  2

---

🔹 8. Code (C++ Tabulation)

int lcs(string s1, string s2) {
    int n = s1.size(), m = s2.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(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]);
        }
    }
    return dp[n][m];
}

---

🔹 9. Space Optimization (Important 🔥)

Use only 2 rows:

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

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

---

🔹 10. Printing the LCS String

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

    // build dp
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            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]);
        }
    }

    // backtrack
    string ans="";
    int i=n, j=m;
    while(i>0 && j>0){
        if(s1[i-1]==s2[j-1]){
            ans += s1[i-1];
            i--; j--;
        }
        else if(dp[i-1][j] > dp[i][j-1]) i--;
        else j--;
    }

    reverse(ans.begin(), ans.end());
    return ans;
}

---

🔹 11. Time & Space Complexity

Approach	Time	Space
Recursion	Exponential	O(n+m)
DP	O(n*m)	O(n*m)
Optimized	O(n*m)	O(m)

---

🔥 12. Important Variations (VERY IMPORTANT)

---

✅ 1. Longest Common Substring

• Must be continuous

if match → dp[i][j] = 1 + dp[i-1][j-1]
else → 0

---

✅ 2. Print Shortest Common Supersequence

Formula:

SCS length = n + m - LCS

---

✅ 3. Minimum Insertions/Deletions to Convert String

Operations = (n - LCS) + (m - LCS)

---

✅ 4. Longest Palindromic Subsequence

👉 Trick:

LPS(s) = LCS(s, reverse(s))

---

✅ 5. Minimum Insertions to Make Palindrome

n - LPS

---

✅ 6. Distinct Subsequences (Related DP)

Different concept but similar DP structure.

---

🧠 13. Key Patterns (Must Remember)

👉 If you see:

• Two strings
• “common”
• “subsequence”
• “insert/delete”

➡️ Think LCS immediately

---

⚡ 14. Interview Tips

• Always start with recursion → convert to DP
• Watch indices (i-1, j-1) carefully
• Practice printing LCS (commonly asked)
• Space optimization is a bonus point

---

🎯 15. Summary

• LCS is a 2D DP problem
• Core idea:

Match → diagonal +1
Not match → max(top, left)