Question

How to find the length of the longest common subsequence (LCS) in two strings with C#

Answer 1

using System;

class Program {
    static int mymax(int a, int b) { 
        return (a > b) ? a : b; 
    } 
    
    static int lcs(String s1, String s2, int lens1, int lens2) { 
        if (lens1 == 0 || lens2 == 0) 
            return 0; 
        if (s1[lens1 - 1] == s2[lens2 - 1]) 
            return 1 + lcs(s1, s2, lens1 - 1, lens2 - 1); 
        else
            return mymax(lcs(s1, s2, lens1, lens2 - 1), lcs(s1, s2, lens1 - 1, lens2)); 
    } 
    static void Main() {
        String s1 = "accyrb";
        String s2 = "cyxyazb";
  
        Console.WriteLine("Length of LCS is {0}", lcs(s1, s2, s1.Length, s2.Length)); 
      }
}



/*
run:

Length of LCS is 3

*/

 

70+ SQL courses for beginners and professionals

Answer 2

using System;

/*
    This program computes BOTH:
      1. The length of the Longest Common Subsequence (LCS)
      2. The actual LCS subsequence

    It uses an efficient dynamic‑programming algorithm:
        Time:  O(n * m)
        Space: O(n * m)

    dp[i][j] stores the LCS length between:
        s1[0..i-1] and s2[0..j-1]

    Recurrence:
        If characters match:
            dp[i][j] = dp[i-1][j-1] + 1
        Else:
            dp[i][j] = Math.Max(dp[i-1][j], dp[i][j-1])

    After filling the DP table, we reconstruct the LCS by
    walking backwards from dp[n][m].
*/

class Program
{
    // Function that returns both LCS length and the subsequence
    static (int length, string sequence) LCS(string s1, string s2)
    {
        int n = s1.Length;
        int m = s2.Length;

        // DP table
        int[,] dp = new int[n + 1, m + 1];

        // Fill DP table
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; 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]);
                }
            }
        }

        // Reconstruct the LCS sequence
        int index = dp[n, m];
        char[] lcsChars = new char[index];

        int x = n, y = m;

        while (x > 0 && y > 0) {
            if (s1[x - 1] == s2[y - 1]) {
                lcsChars[index - 1] = s1[x - 1];
                index--;
                x--;
                y--;
            }
            else if (dp[x - 1, y] > dp[x, y - 1]) {
                x--; // Move up
            }
            else {
                y--; // Move left
            }
        }

        return (dp[n, m], new string(lcsChars));
    }

    static void Main()
    {
        string s1 = "AGGTAB";
        string s2 = "GXTXAYB";

        var result = LCS(s1, s2);

        Console.WriteLine("String 1: " + s1);
        Console.WriteLine("String 2: " + s2);
        Console.WriteLine("Length of LCS: " + result.length);
        Console.WriteLine("LCS sequence: " + result.sequence);
    }
}


/*
run:

String 1: AGGTAB
String 2: GXTXAYB
Length of LCS: 4
LCS sequence: GTAB

*/

 

70+ SQL courses for beginners and professionals