Longest Common Subsequence in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of LCS length calculation

What is the output of the following C++ code that calculates the length of the Longest Common Subsequence (LCS) between two strings?

DSA C++

int lcsLength(const string &X, const string &Y) {
    int m = X.size(), n = Y.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (X[i - 1] == Y[j - 1])
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    return dp[m][n];
}

int main() {
    string X = "AGGTAB";
    string Y = "GXTXAYB";
    cout << lcsLength(X, Y) << endl;
    return 0;
}

A 4

B 3

C 6

D 5

💡 Hint

Trace the matching characters between the two strings and count the longest sequence.

The longest common subsequence between "AGGTAB" and "GXTXAYB" is "GTAB", which has length 4. The code correctly computes and prints 4.

❓ Predict Output

intermediate

Output of LCS sequence reconstruction

What is the output of the following C++ code that reconstructs and prints the Longest Common Subsequence (LCS) between two strings?

DSA C++

string lcsSequence(const string &X, const string &Y) {
    int m = X.size(), n = Y.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (X[i - 1] == Y[j - 1])
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    int i = m, j = n;
    string lcs = "";
    while (i > 0 && j > 0) {
        if (X[i - 1] == Y[j - 1]) {
            lcs = X[i - 1] + lcs;
            i--;
            j--;
        } else if (dp[i - 1][j] > dp[i][j - 1]) {
            i--;
        } else {
            j--;
        }
    }
    return lcs;
}

int main() {
    string X = "ABCBDAB";
    string Y = "BDCABA";
    cout << lcsSequence(X, Y) << endl;
    return 0;
}

A BCBA

B BCAB

C BDAB

D BDCB

💡 Hint

Trace back from dp[m][n] to find the common characters in order.

The longest common subsequence between "ABCBDAB" and "BDCABA" is "BDAB". The code reconstructs this sequence correctly.

🧠 Conceptual

advanced

Time complexity of LCS dynamic programming solution

What is the time complexity of the classic dynamic programming solution to find the length of the Longest Common Subsequence (LCS) of two strings of lengths m and n?

A O(2^(m + n))

B O(m + n)

C O(m^2 + n^2)

D O(m * n)

💡 Hint

Consider the size of the DP table and how many cells are filled.

The DP table has size (m+1)*(n+1), and each cell is computed in constant time, so total time is O(m*n).

🔧 Debug

advanced

Identify the error in LCS length calculation code

What error will the following C++ code produce when trying to calculate the LCS length?

DSA C++

int lcsLength(const string &X, const string &Y) {
    int m = X.size(), n = Y.size();
    vector<vector<int>> dp(m, vector<int>(n, 0));
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (X[i - 1] == Y[j - 1])
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    return dp[m - 1][n - 1];
}

A Runtime error: out of range access

B Compilation error: missing return statement

C Logical error: returns incorrect LCS length

D No error, works correctly

💡 Hint

Check the size of dp and the indices used to access it.

The dp vector is sized m x n but the loops access dp[i][j] for i and j up to m and n inclusive, causing out of range access.

🚀 Application

expert

Number of distinct LCS sequences

Given two strings X and Y, which approach correctly counts the number of distinct Longest Common Subsequences (LCS) between them?

A Use recursion with memoization to count sequences, ignoring length comparisons.

B Use a DP table to store lengths and another DP table to count sequences, updating counts when lengths match or increase.

C Count all common subsequences and filter those with maximum length after enumeration.

D Use a greedy approach to pick matching characters and count sequences directly.

💡 Hint

Think about how to track both length and count simultaneously in DP.

The correct method uses two DP tables: one for LCS length and one for counting sequences, updating counts carefully when lengths tie or increase.

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