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#

using System;

class Program {
    static int LCSLength(string s1, string s2) {
        int m = s1.Length, n = s2.Length;
        int[,] dp = new int[m + 1, n + 1];

        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] = Math.Max(dp[i - 1, j], dp[i, j - 1]);
                }
            }
        }
        return dp[m, n];
    }

    static void Main() {
        string a = "AGGTAB";
        string b = "GXTXAYB";
        Console.WriteLine(LCSLength(a, b));
    }
}

A 5

B 4

C 6

D 7

💡 Hint

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

The longest common subsequence between "AGGTAB" and "GXTXAYB" is "GTAB" which has length 4. The code correctly returns 4, corresponding to option A.

❓ Predict Output

intermediate

Output of LCS string reconstruction

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

DSA C#

using System;
using System.Text;

class Program {
    static string LCS(string s1, string s2) {
        int m = s1.Length, n = s2.Length;
        int[,] dp = new int[m + 1, n + 1];

        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] = Math.Max(dp[i - 1, j], dp[i, j - 1]);
                }
            }
        }

        StringBuilder lcs = new StringBuilder();
        int x = m, y = n;
        while (x > 0 && y > 0) {
            if (s1[x - 1] == s2[y - 1]) {
                lcs.Insert(0, s1[x - 1]);
                x--;
                y--;
            } else if (dp[x - 1, y] > dp[x, y - 1]) {
                x--;
            } else {
                y--;
            }
        }
        return lcs.ToString();
    }

    static void Main() {
        string a = "ABCBDAB";
        string b = "BDCABA";
        Console.WriteLine(LCS(a, b));
    }
}

A BCBA

B BCAB

C BDAB

D BDABA

💡 Hint

Follow the dp table from bottom-right to top-left to reconstruct the LCS.

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

🔧 Debug

advanced

Identify the error in LCS length code

What error does the following C# code produce when trying to calculate the LCS length?

DSA C#

using System;

class Program {
    static int LCSLength(string s1, string s2) {
        int m = s1.Length, n = s2.Length;
        int[,] dp = new int[m, n];

        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] = Math.Max(dp[i - 1, j], dp[i, j - 1]);
                }
            }
        }
        return dp[m - 1, n - 1];
    }

    static void Main() {
        string a = "ABC";
        string b = "AC";
        Console.WriteLine(LCSLength(a, b));
    }
}

A No error, outputs 2

B NullReferenceException

C Returns incorrect LCS length

D IndexOutOfRangeException

💡 Hint

Check how the dp array is declared and accessed with indices starting at 1.

The dp array is declared with size [m, n], but the loops access dp[i, j] where i and j go up to m and n inclusive, causing index out of range.

🚀 Application

advanced

Number of distinct LCS sequences

Given two strings, how can you modify the LCS dynamic programming approach to count the number of distinct longest common subsequences?

A Add a second dp array to count sequences, update counts when dp values match or increase

B Use recursion without memoization to count all subsequences and filter longest

C Count sequences only when characters match, ignore dp values

D Count sequences by multiplying lengths of matching subsequences

💡 Hint

Think about tracking counts alongside lengths in the dp table.

To count distinct LCS sequences, maintain a count dp array that updates counts when dp values increase or match, ensuring all distinct sequences are counted.

🧠 Conceptual

expert

Time complexity of LCS and optimization

What is the time complexity of the classic dynamic programming solution for the Longest Common Subsequence problem, and which optimization can reduce space complexity without affecting time complexity?

A Time complexity O(2^(m+n)), optimize space to O(m+n) by pruning

B Time complexity O(m*n), optimize space to O(min(m,n)) by using rolling arrays

C Time complexity O(m^2*n^2), optimize space to O(m*n) by memoization

D Time complexity O(m+n), optimize space to O(1) by using pointers

💡 Hint

Consider the nested loops and how dp table rows can be reused.

The classic LCS solution runs in O(m*n) time. Space can be optimized to O(min(m,n)) by storing only two rows of the dp table at a time.

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