Longest Common Subsequence in DSA C++ - Execution Trace

Concept Flow - Longest Common Subsequence

Start with two strings

↓

Create DP table with size (m+1)x(n+1)

↓

Fill first row and column with 0

↓

For each character pair (i,j):

↓

If chars match: dp[i

↓

Else: dp[i

↓

After filling table, dp[m

↓

Trace back from dp[m

↓

Done

We build a table comparing prefixes of two strings, filling it step-by-step to find the longest common subsequence length, then trace back to get the sequence.

Execution Sample

DSA C++

string s1 = "ABCBDAB";
string s2 = "BDCABA";
int dp[8][7]; // 7+1 x 6+1
// Fill dp and find LCS length and string

This code fills a table to find the longest common subsequence between "ABCBDAB" and "BDCABA".

Execution Table

Step	Operation	Indices (i,j)	Characters Compared	DP Value Computed	DP Table State (partial)
1	Initialize first row and column	(0,0) to (0,6) and (0,0) to (7,0)	N/A	0	[Row0: 0 0 0 0 0 0 0] [Col0: all 0]
2	Compare s1[1]='A' and s2[1]='B'	(1,1)	A vs B	max(dp[0][1], dp[1][0])=0	[... dp[1][1]=0 ...]
3	Compare s1[1]='A' and s2[2]='D'	(1,2)	A vs D	max(dp[0][2], dp[1][1])=0	[... dp[1][2]=0 ...]
4	Compare s1[1]='A' and s2[3]='C'	(1,3)	A vs C	max(dp[0][3], dp[1][2])=0	[... dp[1][3]=0 ...]
5	Compare s1[1]='A' and s2[4]='A'	(1,4)	A vs A	dp[0][3] + 1 = 1	[... dp[1][4]=1 ...]
6	Compare s1[1]='A' and s2[5]='B'	(1,5)	A vs B	max(dp[0][5], dp[1][4])=1	[... dp[1][5]=1 ...]
7	Compare s1[1]='A' and s2[6]='A'	(1,6)	A vs A	dp[0][5] + 1 = 1	[... dp[1][6]=1 ...]
8	Compare s1[2]='B' and s2[1]='B'	(2,1)	B vs B	dp[1][0] + 1 = 1	[... dp[2][1]=1 ...]
9	Compare s1[2]='B' and s2[2]='D'	(2,2)	B vs D	max(dp[1][2], dp[2][1])=1	[... dp[2][2]=1 ...]
10	Compare s1[2]='B' and s2[3]='C'	(2,3)	B vs C	max(dp[1][3], dp[2][2])=1	[... dp[2][3]=1 ...]
11	Compare s1[2]='B' and s2[4]='A'	(2,4)	B vs A	max(dp[1][4], dp[2][3])=1	[... dp[2][4]=1 ...]
12	Compare s1[2]='B' and s2[5]='B'	(2,5)	B vs B	dp[1][4] + 1 = 2	[... dp[2][5]=2 ...]
13	Compare s1[2]='B' and s2[6]='A'	(2,6)	B vs A	max(dp[1][6], dp[2][5])=2	[... dp[2][6]=2 ...]
14	Continue filling dp table similarly for all i=3 to 7 and j=1 to 6	(3..7,1..6)	Compare chars	Fill dp[i][j] accordingly	Partial dp table fills up
15	Final dp[m][n] computed	(7,6)	s1[7]='B', s2[6]='A'	4	Full dp table filled, dp[7][6]=4
16	Trace back from dp[7][6] to find LCS string	Start at (7,6)	Follow dp values to find matching chars	LCS length=4	LCS string = "BDAB"
17	End	N/A	N/A	N/A	LCS length = 4, LCS = "BDAB"

💡 All dp cells filled; traced back to find longest common subsequence string.

Variable Tracker

Variable	Start	After Step 7	After Step 13	After Step 15	Final
i	0	1	2	7	7
j	0	6	6	6	6
dp[1][4]	0	1	1	1	1
dp[2][5]	0	0	2	2	2
dp[7][6]	0	0	0	4	4
LCS String	""	""	""	""	"BDAB"

Key Moments - 3 Insights

Why do we initialize the first row and column of the dp table with zeros?

Because they represent comparisons with empty prefixes of the strings, so the longest common subsequence length is zero there, as shown in step 1 of the execution_table.

Why do we take max(dp[i-1][j], dp[i][j-1]) when characters don't match?

Because the LCS up to (i,j) is the longest subsequence found by either skipping the current character of s1 or s2, as seen in steps like 2 and 3 where characters differ and dp values come from max of neighbors.

How do we find the actual LCS string after filling the dp table?

We trace back from dp[m][n], moving diagonally when characters match and moving up or left when they don't, collecting matched characters, as described in step 16.

Visual Quiz - 3 Questions

Look at the execution_table at step 5, what is the dp value computed for comparing 'A' and 'A'?

A 1

B 2

C 0

D Undefined

💡 Hint

Check the 'DP Value Computed' column at step 5 in the execution_table.

At which step does the dp table first record a value of 2?

A Step 7

B Step 5

C Step 12

D Step 16

💡 Hint

Look for dp values in the 'DP Value Computed' column; step 12 shows dp[2][5] = 2.

If the first characters of both strings matched, how would the dp value at (1,1) change compared to step 2?

A It would remain 0

B It would be 1 instead of 0

C It would be 2

D It would be undefined

💡 Hint

Refer to the logic in the concept_flow and execution_table step 2 where dp[1][1] is computed.

Concept Snapshot

Longest Common Subsequence (LCS):
- Use a 2D dp table of size (m+1)x(n+1) for strings of length m and n.
- dp[i][j] = length of LCS of s1[0..i-1] and s2[0..j-1].
- If chars match: dp[i][j] = dp[i-1][j-1] + 1.
- Else: dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
- Result at dp[m][n]; trace back to get LCS string.

Full Transcript

Longest Common Subsequence finds the longest sequence common to two strings. We create a table dp where dp[i][j] stores the LCS length of prefixes s1[0..i-1] and s2[0..j-1]. We initialize the first row and column with zeros because empty strings have zero common subsequence. For each pair of characters, if they match, we add 1 to dp[i-1][j-1]. If not, we take the maximum of dp[i-1][j] and dp[i][j-1]. After filling the table, dp[m][n] gives the LCS length. We then trace back from dp[m][n] to find the actual subsequence by moving diagonally when characters match or moving up/left otherwise. This method ensures we find the longest common subsequence efficiently.

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