Longest Common Subsequence in DSA C++ - Time & Space Complexity

Time Complexity: Longest Common Subsequence

O(n x m)

Understanding Time Complexity

We want to understand how the time needed to find the longest common subsequence grows as the input strings get longer.

How does the work increase when the strings become bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

This code finds the length of the longest common subsequence between two strings using a 2D table.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Nested loops over both strings filling the dp table.
• How many times: Outer loop runs n times, inner loop runs m times, so total n x m times.

How Execution Grows With Input

As the strings get longer, the work grows by multiplying their lengths.

Input Size (n = length of s1, m = length of s2)	Approx. Operations
10 and 10	100
100 and 100	10,000
1000 and 1000	1,000,000

Pattern observation: Doubling the length of both strings roughly quadruples the work.

Final Time Complexity

Time Complexity: O(n x m)

This means the time needed grows proportionally to the product of the lengths of the two strings.

Common Mistake

[X] Wrong: "The algorithm runs in linear time because it just loops through the strings once."

[OK] Correct: The algorithm uses nested loops, so it checks pairs of characters from both strings, making the work multiply, not just add.

Interview Connect

Understanding this time complexity helps you explain how dynamic programming improves over simple recursion and why this approach is efficient for comparing sequences.

Self-Check

"What if we used recursion without memoization? How would the time complexity change?"

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