Longest Common Subsequence in DSA C++ - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the DP table with zeros.

DSA C++

int dp[m+1][n+1];
for (int i = 0; i <= m; i++) {
    for (int j = 0; j <= n; j++) {
        dp[i][j] = [1];
    }
}

Drag options to blanks, or click blank then click option'

Ai+j

B1

C-1

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Initializing with 1 instead of 0

Using negative values which are incorrect for LCS length

Not initializing the DP table at all

The DP table for LCS is initialized with zeros to represent empty subsequences.

2fill in blank

medium

Complete the code to check if characters match in the two strings.

DSA C++

if (X[i-1] [1] Y[j-1]) {
    dp[i][j] = dp[i-1][j-1] + 1;
}

Drag options to blanks, or click blank then click option'

A!=

B>

C==

D<

Attempts:

3 left

💡 Hint

Common Mistakes

Using inequality instead of equality

Using greater than or less than operators which are invalid for char comparison here

We check if characters at positions i-1 and j-1 are equal to extend the subsequence.

3fill in blank

hard

Fix the error in the else block to correctly update dp[i][j].

DSA C++

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

Drag options to blanks, or click blank then click option'

Adp[i-1][j-1]

Bdp[i][j-1]

Cdp[i][j+1]

Ddp[i+1][j]

Attempts:

3 left

💡 Hint

Common Mistakes

Using indices out of bounds like j+1 or i+1

Using dp[i-1][j-1] which is for matching case

When characters don't match, dp[i][j] is max of dp[i-1][j] and dp[i][j-1].

4fill in blank

hard

Fill both blanks to complete the loop headers for filling the DP table.

DSA C++

for (int [1] = 1; [1] <= m; [1]++) {
    for (int [2] = 1; [2] <= n; [2]++) {
        // fill dp[i][j]
    }
}

Drag options to blanks, or click blank then click option'

Ai

Bj

Ck

Dl

Attempts:

3 left

💡 Hint

Common Mistakes

Using same variable for both loops

Using uncommon variable names causing confusion

The outer loop uses i for string X, inner loop uses j for string Y.

5fill in blank

hard

Fill all three blanks to complete the code that returns the LCS length.

DSA C++

int lcsLength = dp[[1]][[2]];
return [3];

Drag options to blanks, or click blank then click option'

Am

Bn

ClcsLength

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Returning dp[0][0] which is always zero

Returning m or n instead of the computed length

The LCS length is stored at dp[m][n], which we return.

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