Longest Common Subsequence in DSA C++ - Build from Scratch

Longest Common Subsequence

📖 Scenario: You are working on a text comparison tool that helps find similarities between two strings. This is useful in applications like spell checkers, DNA sequence analysis, and file comparison tools.

🎯 Goal: Build a program that finds the length of the Longest Common Subsequence (LCS) between two given strings using dynamic programming.

📋 What You'll Learn

Create two string variables with exact values

Create a 2D vector to store LCS lengths

Use nested loops to fill the 2D vector based on LCS logic

Print the final LCS length

💡 Why This Matters

🌍 Real World

Finding the Longest Common Subsequence helps in comparing DNA sequences, detecting plagiarism, and version control systems to find differences between files.

💼 Career

Understanding dynamic programming and sequence comparison is valuable for software engineers working in bioinformatics, text processing, and software development.

1

Create the input strings

Create two string variables called str1 and str2 with the exact values "AGGTAB" and "GXTXAYB" respectively.

DSA C++

// Your code here

Hint

Use std::string to create the two strings with the exact given values.

2

Create the 2D vector for LCS lengths

Create a 2D vector of integers called dp with dimensions (str1.size() + 1) rows and (str2.size() + 1) columns, initialized with zeros.

DSA C++

std::string str1 = "AGGTAB";
std::string str2 = "GXTXAYB";
// Your code here

Hint

Use std::vector to create a 2D vector with all elements initialized to zero.

3

Fill the 2D vector using nested loops

Use nested for loops with variables i from 1 to str1.size() and j from 1 to str2.size(). Inside the inner loop, if str1[i-1] == str2[j-1], set dp[i][j] = dp[i-1][j-1] + 1. Otherwise, set dp[i][j] = std::max(dp[i-1][j], dp[i][j-1]).

DSA C++

std::string str1 = "AGGTAB";
std::string str2 = "GXTXAYB";

std::vector> dp(str1.size() + 1, std::vector(str2.size() + 1, 0));
// Your code here

Hint

Use two nested loops to fill the dp table based on the LCS rules.

4

Print the length of the Longest Common Subsequence

Print the value of dp[str1.size()][str2.size()] which represents the length of the Longest Common Subsequence.

DSA C++

std::string str1 = "AGGTAB";
std::string str2 = "GXTXAYB";

std::vector> dp(str1.size() + 1, std::vector(str2.size() + 1, 0));

for (size_t i = 1; i <= str1.size(); ++i) {
    for (size_t j = 1; j <= str2.size(); ++j) {
        if (str1[i - 1] == str2[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]);
        }
    }
}
// Your code here

Hint

The final answer is stored in dp[str1.size()][str2.size()]. Use std::cout to print it.

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