Longest Common Subsequence in DSA C++

Mental Model

Find the longest sequence of characters that appear in the same order in both strings, but not necessarily consecutively.

Analogy: Imagine two friends telling stories. The longest common subsequence is like the longest shared part of their stories that both remember in the same order, even if they skip some details.

String1: A B C D G H
String2: A E D F H R

LCS matrix (partial):
    Ø A E D F H R
Ø [0 0 0 0 0 0 0]
A [0 1 1 1 1 1 1]
B [0 1 1 1 1 1 1]
C [0 1 1 1 1 1 1]
D [0 1 1 2 2 2 2]
G [0 1 1 2 2 2 2]
H [0 1 1 2 2 2 3]

Dry Run Walkthrough

Input: String1: "ABCDGH", String2: "AEDFHR"

Goal: Find the longest common subsequence between the two strings

Step 1: Initialize a 2D matrix dp with dimensions (len1+1) x (len2+1) filled with 0

dp matrix filled with zeros:
  Ø A E D F H R
Ø 0 0 0 0 0 0 0
A 0 0 0 0 0 0 0
B 0 0 0 0 0 0 0
C 0 0 0 0 0 0 0
D 0 0 0 0 0 0 0
G 0 0 0 0 0 0 0
H 0 0 0 0 0 0 0

Why: We need a table to store lengths of LCS for substrings to build up the solution

Step 2: Compare characters at positions (1,1): 'A' and 'A', they match, set dp[1][1] = dp[0][0] + 1 = 1

dp matrix updated:
  Ø A E D F H R
Ø 0 0 0 0 0 0 0
A 0 1 0 0 0 0 0
B 0 0 0 0 0 0 0
C 0 0 0 0 0 0 0
D 0 0 0 0 0 0 0
G 0 0 0 0 0 0 0
H 0 0 0 0 0 0 0

Why: Matching characters increase the LCS length by 1 from previous substrings

Step 3: Compare characters at positions (4,3): 'D' and 'D', they match, set dp[4][3] = dp[3][2] + 1 = 2

dp matrix partial:
  Ø A E D F H R
Ø 0 0 0 0 0 0 0
A 0 1 1 1 1 1 1
B 0 1 1 1 1 1 1
C 0 1 1 1 1 1 1
D 0 1 1 2 2 2 2
G 0 1 1 2 2 2 2
H 0 1 1 2 2 2 2

Why: Found another matching character, so LCS length increases

Step 4: Compare characters at positions (6,5): 'H' and 'H', they match, set dp[6][5] = dp[5][4] + 1 = 3

dp matrix final:
  Ø A E D F H R
Ø 0 0 0 0 0 0 0
A 0 1 1 1 1 1 1
B 0 1 1 1 1 1 1
C 0 1 1 1 1 1 1
D 0 1 1 2 2 2 2
G 0 1 1 2 2 2 2
H 0 1 1 2 2 3 3

Why: Last matching character found, final LCS length is 3

Step 5: Trace back from dp[len1][len2] to find the LCS string: start at dp[6][6]

Trace back path:
Positions matched: (6,5) 'H', (4,3) 'D', (1,1) 'A'
LCS string: "ADH"

Why: Backtracking recovers the actual longest common subsequence

Result:

dp matrix final:
  Ø A E D F H R
Ø 0 0 0 0 0 0 0
A 0 1 1 1 1 1 1
B 0 1 1 1 1 1 1
C 0 1 1 1 1 1 1
D 0 1 1 2 2 2 2
G 0 1 1 2 2 2 2
H 0 1 1 2 2 3 3

Longest Common Subsequence: ADH

Annotated Code

DSA C++

#include <iostream>
#include <vector>
#include <string>
using namespace std;

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

    // Build dp matrix
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (s1[i - 1] == s2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;  // match found, increase length
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);  // take max of ignoring one char
            }
        }
    }

    // Backtrack to find LCS string
    int i = n, j = m;
    string lcs = "";
    while (i > 0 && j > 0) {
        if (s1[i - 1] == s2[j - 1]) {
            lcs = s1[i - 1] + lcs;  // add matching char
            --i; --j;  // move diagonally up-left
        } else if (dp[i - 1][j] > dp[i][j - 1]) {
            --i;  // move up
        } else {
            --j;  // move left
        }
    }
    return lcs;
}

int main() {
    string s1 = "ABCDGH";
    string s2 = "AEDFHR";
    string result = longestCommonSubsequence(s1, s2);
    cout << "Longest Common Subsequence: " << result << endl;
    return 0;
}

if (s1[i - 1] == s2[j - 1]) { dp[i][j] = dp[i - 1][j - 1] + 1;

match found, increase LCS length by 1 from previous substrings

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

no match, take max LCS length by ignoring one character from either string

while (i > 0 && j > 0) { if (s1[i - 1] == s2[j - 1]) { lcs = s1[i - 1] + lcs; --i; --j;

backtrack diagonally when characters match to build LCS string

else if (dp[i - 1][j] > dp[i][j - 1]) { --i;

move up in dp matrix if top cell has larger LCS length

else { --j;

move left in dp matrix if left cell has larger or equal LCS length

Output

Longest Common Subsequence: ADH

Complexity Analysis

Time: O(n*m) because we fill a matrix of size n by m once

Space: O(n*m) because we store LCS lengths for all substring pairs

vs Alternative: Naive recursive approach has exponential time due to repeated subproblems; DP reduces it to polynomial time

Edge Cases

One or both strings empty

LCS length is zero and result is empty string

DSA C++

vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));

Strings with no common characters

LCS length is zero and result is empty string

DSA C++

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

Strings are identical

LCS is the entire string

DSA C++

if (s1[i - 1] == s2[j - 1]) {
    dp[i][j] = dp[i - 1][j - 1] + 1;

When to Use This Pattern

When asked to find the longest sequence common to two sequences in order but not necessarily contiguous, use the Longest Common Subsequence pattern with dynamic programming.

Common Mistakes

Mistake: Not initializing the dp matrix with zeros causing garbage values
Fix: Initialize dp with zeros for base cases to handle empty substrings

Mistake: Incorrectly backtracking the dp matrix leading to wrong LCS string
Fix: Backtrack by moving diagonally on match, else move towards the direction of larger dp value

Mistake: Confusing substring indices causing off-by-one errors
Fix: Use 1-based indexing for dp and adjust string indices by subtracting 1

Summary

Finds the longest sequence of characters common to both strings in order.

Use when you need to compare two sequences and find their longest shared pattern.

Build a matrix of LCS lengths for substrings and backtrack to get the sequence.

Practice

1. What does the Longest Common Subsequence (LCS) between two strings represent?

easy

A. The longest substring that appears exactly the same in both strings.

B. The longest sequence of characters that appear in both strings in the same order, but not necessarily consecutively.

C. The shortest sequence of characters that can be formed from both strings.

D. The total number of characters in both strings combined.

Solution

1. Step 1: Understand the definition of LCS

   The LCS is a sequence that appears in both strings in the same order but not necessarily consecutively.

2. Step 2: Differentiate LCS from substring

   Unlike substring, LCS does not require characters to be consecutive, only order matters.

3. Final Answer:

   The longest sequence of characters that appear in both strings in the same order, but not necessarily consecutively. -> Option B

4. Quick Check:

   LCS = longest ordered sequence [OK]

Hint: LCS keeps order but skips characters if needed [OK]

Common Mistakes:

• Confusing LCS with longest substring
• Thinking LCS characters must be consecutive
• Mixing LCS with string length or concatenation

2. Which of the following is the correct way to declare a 2D vector dp of size m+1 by n+1 initialized with zeros in C++ for LCS dynamic programming?

easy

A. std::vector<int> dp(m+1, n+1, 0);

B. std::vector dp(m+1, std::vector<int>(n+1));

C. std::vector dp(m, n, 0);

D. std::vector dp(m+1, std::vector<int>(n+1, 0));

Solution

1. Step 1: Understand vector initialization syntax

   To create a 2D vector, use nested vectors with sizes and initial values specified.

2. Step 2: Check each option

   std::vector dp(m+1, std::vector<int>(n+1, 0)); correctly creates a vector of size m+1, each containing a vector of size n+1 initialized to 0.

3. Final Answer:

   std::vector dp(m+1, std::vector<int>(n+1, 0)); -> Option D

4. Quick Check:

   Correct 2D vector syntax = std::vector dp(m+1, std::vector<int>(n+1, 0)); [OK]

Hint: Use nested vector constructor with size and initial value [OK]

Common Mistakes:

• Using wrong vector constructor parameters
• Missing initialization value for inner vectors
• Confusing 1D and 2D vector declarations

3. What is the output of the following C++ code snippet that calculates the length of LCS for strings s1 = "ABCBDAB" and s2 = "BDCABA"?

std::string s1 = "ABCBDAB";
std::string s2 = "BDCABA";
int m = s1.size();
int n = s2.size();
std::vector dp(m+1, std::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] = std::max(dp[i-1][j], dp[i][j-1]);
  }
}
std::cout << dp[m][n] << std::endl;

medium

A. 5

B. 3

C. 4

D. 6

Solution

1. Step 1: Understand the DP table filling

   The code fills dp table comparing characters of s1 and s2, increasing count when characters match.

2. Step 2: Trace LCS length for given strings

   The LCS for "ABCBDAB" and "BDCABA" is "BDAB" or "BCBA" with length 4, but actually the longest common subsequence length is 4 or 5? Let's verify carefully.

3. Step 3: Verify LCS length

   Common subsequences include "BCBA" (length 4), "BDAB" (length 4), but also "BCAB" (length 4). However, the classic known LCS length for these strings is 4. But let's check carefully:
4. Check sequences:
   • "BCBA" (B C B A) length 4
   • "BDAB" (B D A B) length 4
   • Is there a longer subsequence? "BCBAB" is not possible due to order.
5. Therefore, the length is 4.

6. Final Answer:

   4 -> Option C

7. Quick Check:

   LCS length = 4 [OK]

Hint: Trace DP table or recall classic LCS example [OK]

Common Mistakes:

• Counting longest substring instead of subsequence
• Off-by-one errors in indexing
• Confusing length with number of matches

4. Identify the bug in the following LCS code snippet and select the correct fix:

std::string s1 = "AGGTAB";
std::string s2 = "GXTXAYB";
int m = s1.size();
int n = s2.size();
std::vector dp(m, std::vector<int>(n, 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] = std::max(dp[i-1][j], dp[i][j-1]);
  }
}
std::cout << dp[m][n] << std::endl;

medium

A. Change dp size to (m+1) x (n+1) to avoid out-of-bound errors.

B. Start loops from i=0 and j=0 instead of 1.

C. Remove the else block to fix logic.

D. Use dp[i][j] = dp[i-1][j-1] + 2 when characters match.

Solution

1. Step 1: Check dp vector size and loop indices

   dp is sized m x n but loops run from 1 to m and 1 to n, causing out-of-bound access at dp[m][n].

2. Step 2: Fix dp size to (m+1) x (n+1)

   Allocating dp with size (m+1) x (n+1) matches loop indices and prevents out-of-bound errors.

3. Final Answer:

   Change dp size to (m+1) x (n+1) to avoid out-of-bound errors. -> Option A

4. Quick Check:

   dp size must match loop range [OK]

Hint: dp size = (m+1) x (n+1) for 1-based indexing [OK]

Common Mistakes:

• Allocating dp with size m x n but using 1-based loops
• Ignoring out-of-bound runtime errors
• Incorrectly modifying dp values on match

5. Given two strings s1 = "XMJYAUZ" and s2 = "MZJAWXU", write a C++ function to find the actual Longest Common Subsequence string (not just its length). What is the correct LCS string returned by your function?

hard

A. "MJAU"

B. "MJZU"

C. "MJYU"

D. "MJAU" or "MJYU" depending on path

Solution

1. Step 1: Build dp table for LCS length

   Use standard DP to fill dp table with lengths for substrings of s1 and s2.

2. Step 2: Trace back from dp[m][n] to find LCS string

   Traceback yields "MJAU" of length 4.

3. Final Answer:

   "MJAU" -> Option A

4. Quick Check:

   LCS = "MJAU" [OK]

Hint: Trace back dp table to find the LCS string [OK]

Common Mistakes:

• Assuming only one unique LCS string
• Not tracing back dp table correctly
• Confusing subsequence with substring