Longest Common Subsequence in DSA C# - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the Longest Common Subsequence (LCS)?

LCS is the longest sequence that appears in the same relative order in two sequences, but not necessarily contiguously.

intermediate

How does the LCS dynamic programming approach work?

It builds a 2D table where each cell stores the length of LCS for prefixes of the two sequences, using previous results to find the current one.

beginner

What is the time complexity of the classic LCS algorithm using dynamic programming?

The time complexity is O(m * n), where m and n are the lengths of the two sequences.

beginner

In LCS, what does it mean if characters at current indices match?

If characters match, add 1 to the LCS length from previous indices and move diagonally in the DP table.

intermediate

How do you reconstruct the LCS string from the DP table?

Start from the bottom-right cell and move backwards: if characters match, add to result; else move in direction of larger value.

What does LCS stand for?

A Longest Common Subsequence

B Largest Common Substring

C Longest Continuous Sequence

D Least Common Substring

LCS stands for Longest Common Subsequence.

What is the main idea behind the dynamic programming solution for LCS?

A Divide sequences into halves and solve recursively

B Sort sequences and compare characters

C Build a table storing LCS lengths for all prefix pairs

D Use hashing to find common parts

The DP solution builds a table storing LCS lengths for all prefix pairs.

If characters at current indices do not match, what do you do in the DP table?

A Take the maximum value from left or top cell

B Add 1 to the diagonal cell

C Set current cell to zero

D Ignore and move diagonally

If characters don't match, take the max value from left or top cell in the DP table.

What is the space complexity of the classic LCS DP solution?

A O(max(m, n))

B O(m + n)

C O(1)

D O(m * n)

The classic DP solution uses O(m * n) space for the table.

Which of these is true about the LCS?

A It is always the shortest common subsequence

B It preserves the order of characters in both sequences

C It must be contiguous in both sequences

D It ignores character order

LCS preserves the order of characters in both sequences but not necessarily contiguous.

Explain how to use dynamic programming to find the Longest Common Subsequence between two strings.

Think about building solutions for smaller parts first.

Describe the process to reconstruct the actual LCS string after computing the DP table.

Trace back through the table to find the sequence.

Practice

1. What does the Longest Common Subsequence (LCS) between two strings represent?

easy

A. The longest sequence of characters appearing in both strings in the same order, not necessarily contiguous

B. The longest sequence of consecutive characters shared by both strings

C. The string formed by concatenating both inputs

D. The shortest string that contains both inputs as subsequences

Solution

1. Step 1: Define subsequence

   A subsequence maintains relative order of characters but does not require them to be contiguous. 'ace' is a subsequence of 'abcde'.

2. Step 2: LCS definition

   LCS is the longest such subsequence common to both strings. For 'ABCBDAB' and 'BDCAB', LCS is 'BCAB' or 'BDAB', length 4.

3. Final Answer:

   Longest common subsequence - same order, not necessarily contiguous. -> Option A

4. Quick Check:

   Subsequence = order preserved, not contiguous. LCS = longest shared one. [OK]

Hint: Subsequence = order preserved, gaps allowed. LCS = longest one common to both strings. [OK]

Common Mistakes:

• Confusing subsequence with substring (substring must be contiguous)
• Thinking LCS is the shortest common supersequence
• Assuming characters must be adjacent

2. For strings X = "ABCD" and Y = "ACDF", what is the length of the LCS?

medium

A. 2

B. 3

C. 4

D. 1

Solution

1. Step 1: Find common subsequences

   Characters in both: A, C, D. Check order: A appears before C in both. C appears before D in both. So 'ACD' is a common subsequence of length 3.

2. Step 2: Can we do better?

   'ABCD' and 'ACDF' share A, C, D in order. B is not in Y. F is not in X. No common subsequence of length 4 exists.

3. Final Answer:

   LCS = "ACD", length 3. -> Option B

4. Quick Check:

   A→C→D in both strings: length 3. [OK]

Hint: Trace common characters in order: A(pos 0,0)→C(pos 2,1)→D(pos 3,2) = 3. [OK]

Common Mistakes:

• Counting all common characters without checking order
• Including B which is not in Y
• Stopping at 2 by missing D

3. In the LCS DP recurrence, when X[i] == Y[j], what is dp[i][j]?

medium

A. dp[i-1][j-1]

B. dp[i-1][j-1] + 1

C. max(dp[i-1][j], dp[i][j-1])

D. dp[i][j-1] + 1

Solution

1. Step 1: When characters match

   If X[i] == Y[j], the current characters extend the LCS found without them. We add 1 to the LCS of X[0..i-1] and Y[0..j-1].

2. Step 2: Recurrence

   dp[i][j] = dp[i-1][j-1] + 1. We extend the diagonal neighbor by 1.

3. Step 3: When they don't match

   dp[i][j] = max(dp[i-1][j], dp[i][j-1]) - take the best from skipping either character.

4. Final Answer:

   dp[i-1][j-1] + 1 -> Option B

5. Quick Check:

   Match → diagonal + 1. No match → max of left and above. [OK]

Hint: Match: diagonal + 1. No match: max(left, above). [OK]

Common Mistakes:

• Using dp[i-1][j-1] without adding 1
• Using max formula when characters match
• Adding 1 to dp[i][j-1] instead of diagonal

4. What is the time and space complexity of the standard 2D DP LCS solution for strings of length m and n?

medium

A. Time O(m+n), Space O(m+n)

B. Time O(m×n), Space O(m×n)

C. Time O(m×n), Space O(min(m,n))

D. Time O(2^n), Space O(n)

Solution

1. Step 1: Time complexity

   We fill a 2D table of size (m+1)×(n+1), computing each cell in O(1). Total: O(m×n).

2. Step 2: Space complexity

   The full 2D DP table requires O(m×n) space. Space can be optimized to O(min(m,n)) using two rows, but standard solution uses O(m×n).

3. Final Answer:

   Time O(m×n), Space O(m×n) -> Option B

4. Quick Check:

   Standard 2D table = O(m×n) both time and space. [OK]

Hint: Standard LCS: O(m×n) time and space (2D table). [OK]

Common Mistakes:

• Saying O(m+n) which is linear - LCS needs quadratic
• Reporting space-optimized O(min(m,n)) for the standard solution
• Confusing with exponential recursion without memoization

5. In C#, after filling the LCS DP table for X="AGGTAB" and Y="GXTXAYB", what value does dp[6][7] hold?

hard

A. 3

B. 4

C. 5

D. 6

Solution

1. Step 1: Identify LCS

   X = 'AGGTAB', Y = 'GXTXAYB'. Common subsequences include 'GTAB' (length 4): G(1,0)→T(2,3)→A(4,4)→B(5,6).

2. Step 2: Verify length 4

   G: appears in both at valid positions. T: X[2]='G',X[2]='G'... Let's check: X='A,G,G,T,A,B'. Y='G,X,T,X,A,Y,B'. Common: G(X[1],Y[0]), T(X[3],Y[2]), A(X[4],Y[4]), B(X[5],Y[6]) → GTAB length 4.

3. Final Answer:

   dp[6][7] = 4 -> Option B

4. Quick Check:

   LCS of 'AGGTAB' and 'GXTXAYB' is 'GTAB' = length 4. [OK]

Hint: LCS('AGGTAB','GXTXAYB') = 'GTAB' = 4. This is a classic example - memorize it. [OK]

Common Mistakes:

• Confusing LCS length with string length
• Incorrectly tracing the DP table
• Getting 3 by missing one character in the subsequence