Longest Common Subsequence in DSA C#

Mental Model

Find the longest sequence of characters that appear in the same order in both strings, but not necessarily consecutively.

Analogy: Imagine two friends telling stories with some common events. The longest common subsequence is like the longest list of shared events they both mention in the same order, even if they skip some details.

String1: A B C D G H
String2: A E D F H R

LCS path:
A ->   -> D ->   -> H

Positions:
String1: A B C D G H
          ↑     ↑     ↑
String2: A E D F H R
          ↑     ↑     ↑

Dry Run Walkthrough

Input: String1: "ABCDGH", String2: "AEDFHR"

Goal: Find the longest common subsequence between the two strings

Step 1: Initialize a 2D table with dimensions (length of String1 + 1) x (length of String2 + 1) filled with zeros

[[0,0,0,0,0,0,0],
 [0,0,0,0,0,0,0],
 [0,0,0,0,0,0,0],
 [0,0,0,0,0,0,0],
 [0,0,0,0,0,0,0],
 [0,0,0,0,0,0,0],
 [0,0,0,0,0,0,0]]

Why: We need this table to store lengths of LCS for substrings to build up the solution

Step 2: Compare characters 'A' (String1[0]) and 'A' (String2[0]), they match, set table[1][1] = 1 + table[0][0] = 1

[[0,0,0,0,0,0,0],
 [0,1,0,0,0,0,0],
 [0,0,0,0,0,0,0],
 [0,0,0,0,0,0,0],
 [0,0,0,0,0,0,0],
 [0,0,0,0,0,0,0],
 [0,0,0,0,0,0,0]]

Why: Matching characters increase LCS length by 1 from previous substrings

Step 3: Compare 'B' (String1[1]) and 'E' (String2[1]), no match, set table[2][2] = max(table[1][2], table[2][1]) = 1

[[0,0,0,0,0,0,0],
 [0,1,0,0,0,0,0],
 [0,1,1,0,0,0,0],
 [0,0,0,0,0,0,0],
 [0,0,0,0,0,0,0],
 [0,0,0,0,0,0,0],
 [0,0,0,0,0,0,0]]

Why: No match means LCS length is max of ignoring one character from either string

Step 4: Compare 'D' (String1[3]) and 'D' (String2[2]), match, set table[4][3] = 1 + table[3][2] = 2

[[0,0,0,0,0,0,0],
 [0,1,0,0,0,0,0],
 [0,1,1,0,0,0,0],
 [0,1,1,1,0,0,0],
 [0,1,1,2,0,0,0],
 [0,0,0,0,0,0,0],
 [0,0,0,0,0,0,0]]

Why: Matching characters extend the LCS by 1 from previous substrings

Step 5: Compare 'H' (String1[5]) and 'H' (String2[4]), match, set table[6][5] = 1 + table[5][4] = 3

[[0,0,0,0,0,0,0],
 [0,1,0,0,0,0,0],
 [0,1,1,0,0,0,0],
 [0,1,1,1,0,0,0],
 [0,1,1,2,2,2,2],
 [0,1,1,2,2,2,2],
 [0,1,1,2,2,3,3]]

Why: Last matching characters increase LCS length to 3

Step 6: Trace back from table[6][6] to find LCS characters: H, D, A

LCS = "ADH"

Why: Backtracking finds the actual longest common subsequence

Result:

Final LCS length table last cell: 3
Longest Common Subsequence: ADH

Annotated Code

DSA C#

using System;

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

        // Build the dp table
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s1[i - 1] == s2[j - 1]) {
                    dp[i, j] = 1 + dp[i - 1, j - 1];
                } else {
                    dp[i, j] = Math.Max(dp[i - 1, j], dp[i, j - 1]);
                }
            }
        }

        // Backtrack to find the LCS string
        int index = dp[m, n];
        char[] lcs = new char[index];
        int x = m, y = n;
        while (x > 0 && y > 0) {
            if (s1[x - 1] == s2[y - 1]) {
                lcs[index - 1] = s1[x - 1];
                x--;
                y--;
                index--;
            } else if (dp[x - 1, y] > dp[x, y - 1]) {
                x--;
            } else {
                y--;
            }
        }

        return new string(lcs);
    }

    static void Main() {
        string s1 = "ABCDGH";
        string s2 = "AEDFHR";
        string result = FindLCS(s1, s2);
        Console.WriteLine("Longest Common Subsequence: " + result);
    }
}

if (s1[i - 1] == s2[j - 1]) { dp[i, j] = 1 + dp[i - 1, j - 1]; } else { dp[i, j] = Math.Max(dp[i - 1, j], dp[i, j - 1]); }

Fill dp table by extending LCS length if characters match, else take max from previous substrings

while (x > 0 && y > 0) { if (s1[x - 1] == s2[y - 1]) { lcs[index - 1] = s1[x - 1]; x--; y--; index--; } else if (dp[x - 1, y] > dp[x, y - 1]) { x--; } else { y--; } }

Backtrack dp table to reconstruct the LCS string by moving diagonally on match or up/left otherwise

Output

Longest Common Subsequence: ADH

Complexity Analysis

Time: O(m*n) because we fill a table of size m by n once

Space: O(m*n) because we store LCS lengths for all substring pairs in a 2D table

vs Alternative: Naive recursive approach is exponential due to repeated subproblems; DP reduces it to polynomial time

Edge Cases

One or both strings empty

LCS length is zero and returned string is empty

DSA C#

int m = s1.Length; int n = s2.Length;

No common characters

LCS length is zero and returned string is empty

DSA C#

dp[i, j] = Math.Max(dp[i - 1, j], dp[i, j - 1]);

Strings are identical

LCS is the entire string itself

DSA C#

if (s1[i - 1] == s2[j - 1]) { dp[i, j] = 1 + dp[i - 1, j - 1]; }

When to Use This Pattern

When you need to find the longest sequence common to two sequences in order, use the Longest Common Subsequence pattern because it efficiently finds shared order without requiring contiguity.

Common Mistakes

Mistake: Confusing subsequence with substring and expecting characters to be consecutive
Fix: Remember subsequence allows skipping characters; focus on order, not adjacency

Mistake: Not initializing dp table with zeros causing incorrect base cases
Fix: Initialize dp table with zeros to represent empty substring comparisons

Mistake: Incorrect backtracking direction leading to wrong LCS reconstruction
Fix: Backtrack diagonally on match, else move towards the direction with larger dp value

Summary

Finds the longest sequence of characters appearing in order in both strings.

Use when comparing two sequences to find their shared ordered pattern.

The key is building a table of solutions for smaller substrings and backtracking to get 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