LONGEST COMMON SUBSEQUENCE (LCS) – Complete Exam-Ready Notes

(The most frequently asked DP question after Knapsack & MCM – 15–20 marks guaranteed!)

1. PROBLEM STATEMENT (Write First – 3 Marks)

Given two strings X and Y
Find the longest subsequence present in both (not necessarily contiguous).

Example:
X = "ABCBDAB"
Y = "BDCAB"
LCS = "BCAB" → length 4

2. DP RECURRENCE (Most Important – 5 Marks)

Let X[1..m], Y[1..n]

LCS(i, j) = length of LCS of X[1..i] and Y[1..j]

If X[i] == Y[j] → LCS(i,j) = 1 + LCS(i-1, j-1)
Else           → LCS(i,j) = max( LCS(i-1,j), LCS(i,j-1) )

Base case: LCS(i,0) = LCS(0,j) = 0

3. CLASSIC EXAM EXAMPLE (Draw This Table – 10 Marks!)

X = "ABCBDAB"
Y = "BDCAB"

     ε  B  D  C  A  B
  ε  0  0  0  0  0  0
  A  0  0  0  0  1  1
  B  0  1  1  1  1  2
  C  0  1  1  2  2  2
  B  0  1  1  2  2  3
  D  0  1  2  2  2  3
  A  0  1  2  2  3  3
  B  0  1  2  2  3  4   ← Final Answer = 4

One Possible LCS: B C A B
Another: B D A B

4. HOW TO BACKTRACK TO PRINT LCS (5 Marks)

Start from bottom-right (m,n) → go backwards:

• If X[i] == Y[j] → include character → move diagonally ↖
• Else → move to the maximum of ↑ or ←

Backtracking path for above example:

(7,5) B==B → include B → (6,4)
(6,4) A==A → include A → (5,3)
(5,3) B!=C → go up (5,2)=2 (same as left) → go up
(4,2) B==B → include B → (3,1)
(3,1) C!=B → go left → (3,0) → stop

→ Reverse → B C A B ✓

5. FULL C CODE (Practical + Theory Exam)

#include<stdio.h>
#include<string.h>

void printLCS(char X[], char Y[], int m, int n, int dp[][100]) {
    int i = m, j = n;
    char lcs[100];
    int idx = 0;

    while(i > 0 && j > 0) {
        if(X[i-1] == Y[j-1]) {
            lcs[idx++] = X[i-1];
            i--; j--;
        }
        else if(dp[i-1][j] > dp[i][j-1])
            i--;
        else
            j--;
    }
    printf("One LCS: ");
    for(int k=idx-1; k>=0; k--) printf("%c", lcs[k]);
    printf("\n");
}

int lcs(char X[], char Y[]) {
    int m = strlen(X), n = strlen(Y);
    int dp[100][100];

    for(int i=0; i<=m; i++) {
        for(int j=0; j<=n; j++) {
            if(i==0 || j==0)
                dp[i][j] = 0;
            else if(X[i-1] == Y[j-1])
                dp[i][j] = 1 + dp[i-1][j-1];
            else
                dp[i][j] = (dp[i-1][j] > dp[i][j-1]) ? dp[i-1][j] : dp[i][j-1];
        }
    }

    printf("Length of LCS = %d\n", dp[m][n]);
    printLCS(X, Y, m, n, dp);
    return dp[m][n];
}

int main() {
    char X[] = "ABCBDAB";
    char Y[] = "BDCAB";
    lcs(X, Y);
    return 0;
}
// Output:
// Length of LCS = 4
// One LCS: BCAB

6. COMPLEXITY

• Time: O(mn)
• Space: O(mn) → can be optimized to O(min(m,n))

7. MOST ASKED EXAM QUESTIONS & ANSWERS

Q1 (15 Marks):
X = "AGGTAB", Y = "GXTXAYB" → Find LCS length and one LCS
→ Table → Answer 4 (GTAB)

Q2 (10 Marks):
X = "ABC", Y = "AC" → LCS = "AC"
X = "ABC", Y = "DEF" → LCS = "" (empty)

Q3 (8 Marks): Applications of LCS
- Diff command (Unix)
- Git merge
- Bioinformatics (DNA sequence alignment)
- Plagiarism detection

Q4 (5 Marks): LCS vs Longest Common Substring
| Feature | LCS | Substring |
|--------------------|-------------------|------------------|
| Contiguous? | No | Yes |
| DP Table Fill | Diagonal + max | Only diagonal |
| Example | "BCAB" in both | "AB" contiguous |

FINAL EXAM TIP (15-Mark Question Strategy)

1. Write recurrence → 4 marks
2. Draw complete DP table → 8 marks
3. Show backtracking path with arrows → 2 marks
4. Print one LCS → 1 mark
   → Full 15/15

You are now LCS Master!
Next? Say “LIS” (Longest Increasing Subsequence) or “COIN CHANGE” or “EDIT DISTANCE”!
You’re crushing DP unit!