Longest Common Subsequence in DSA C# - Build from Scratch

Longest Common Subsequence

📖 Scenario: Imagine you are comparing two versions of a document to find the longest sequence of words that appear in both versions in the same order. This helps in understanding how much content is shared between the two versions.

🎯 Goal: You will build a program that finds the length of the longest common subsequence (LCS) between two strings. The LCS is the longest sequence of characters that appear in both strings in the same order, but not necessarily consecutively.

📋 What You'll Learn

Create two string variables with exact values

Create a 2D integer array to store LCS lengths

Implement nested loops to fill the LCS table using dynamic programming

Print the length of the longest common subsequence

💡 Why This Matters

🌍 Real World

Finding common subsequences is useful in text comparison tools, DNA sequence analysis, and version control systems to detect similarities.

💼 Career

Understanding dynamic programming and sequence comparison is valuable for software engineers working on algorithms, bioinformatics, and data analysis.

1

Create the input strings

Create two string variables called firstString and secondString with these exact values: "AGGTAB" and "GXTXAYB" respectively.

DSA C#

# Your code here

Hint

Use string type and assign the exact text inside double quotes.

2

Create the LCS table

Create a 2D integer array called lcsTable with dimensions firstString.Length + 1 by secondString.Length + 1.

DSA C#

string firstString = "AGGTAB";
string secondString = "GXTXAYB";
// Create the 2D array lcsTable here
# Your code here

Hint

Use new int[rows, columns] to create a 2D array in C#.

3

Fill the LCS table using nested loops

Use nested for loops with variables i from 1 to firstString.Length and j from 1 to secondString.Length. Inside the inner loop, if firstString[i - 1] equals secondString[j - 1], set lcsTable[i, j] to lcsTable[i - 1, j - 1] + 1. Otherwise, set lcsTable[i, j] to the maximum of lcsTable[i - 1, j] and lcsTable[i, j - 1].

DSA C#

string firstString = "AGGTAB";
string secondString = "GXTXAYB";
int[,] lcsTable = new int[firstString.Length + 1, secondString.Length + 1];
// Fill the lcsTable using nested loops
# Your code here

Hint

Remember to start loops from 1 because the 0th row and column are for empty prefixes.

4

Print the length of the longest common subsequence

Print the value at lcsTable[firstString.Length, secondString.Length] using Console.WriteLine.

DSA C#

string firstString = "AGGTAB";
string secondString = "GXTXAYB";
int[,] lcsTable = new int[firstString.Length + 1, secondString.Length + 1];

for (int i = 1; i <= firstString.Length; i++)
{
    for (int j = 1; j <= secondString.Length; j++)
    {
        if (firstString[i - 1] == secondString[j - 1])
        {
            lcsTable[i, j] = lcsTable[i - 1, j - 1] + 1;
        }
        else
        {
            lcsTable[i, j] = Math.Max(lcsTable[i - 1, j], lcsTable[i, j - 1]);
        }
    }
}
// Print the LCS length below
# Your code here

Hint

The final answer is the value in the bottom-right cell of the table.

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