Longest Common Subsequence in c#

General
1

The Longest Common Subsequence (LCS) problem involves finding the longest subsequence that is common to two given sequences. Unlike substrings, the characters in a subsequence do not need to be contiguous but must maintain their relative order.

Algorithm Explanation

The LCS can be efficiently solved using dynamic programming:

  1. Dynamic Programming Table: Create a 2D array dp where dp[i][j] represents the length of the longest common subsequence of the first i characters of str1 and the first j characters of str2.

  2. Initialization: Initialize the first row and the first column of the table to 0, since the LCS of any string with an empty string is 0.

  3. Filling the DP Table:

    • Loop through each character in both strings.
    • If the characters match (str1[i-1] == str2[j-1]), then dp[i][j] = dp[i-1][j-1] + 1.
    • If they do not match, take the maximum value from the left or above: dp[i][j] = Math.Max(dp[i-1][j], dp[i][j-1]).

  4. Result: The value in dp[m][n] (where m and n are the lengths of the two strings) will be the length of the longest common subsequence.

C# Implementation

Here’s how you can implement the LCS problem in C#:

using System;

class Program
{
    static void Main()
    {
        string str1 = "AGGTAB";
        string str2 = "GXTXAYB";
        int result = LongestCommonSubsequence(str1, str2);
        Console.WriteLine("Length of Longest Common Subsequence: " + result);
    }

    static int LongestCommonSubsequence(string str1, string str2)
    {
        int m = str1.Length;
        int n = str2.Length;
        int[,] dp = new int[m + 1, n + 1]; // DP table to store lengths

        // Fill the DP table
        for (int i = 1; i <= m; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                // Check for matching characters
                if (str1[i - 1] == str2[j - 1])
                {
                    dp[i, j] = dp[i - 1, j - 1] + 1; // Increment length
                }
                else
                {
                    dp[i, j] = Math.Max(dp[i - 1, j], dp[i, j - 1]); // Max from left or above
                }
            }
        }

        return dp[m, n]; // Return the length of the longest common subsequence
    }
}

Explanation of Code

  1. Input: The program defines two strings, str1 and str2, for which it will find the longest common subsequence.
  2. LongestCommonSubsequence Function:
    • Initializes a 2D array dp with dimensions (m + 1) x (n + 1), where m and n are the lengths of str1 and str2, respectively.
  3. Filling the DP Table:
    • The outer loop iterates through the characters of str1, and the inner loop iterates through the characters of str2.
    • When a match is found, it increments the LCS length stored in dp[i, j].
    • If the characters do not match, it takes the maximum length from either the left (dp[i, j - 1]) or above (dp[i - 1, j]).
  4. Return Result: The function returns dp[m, n], which contains the length of the longest common subsequence.

Complexity

  • Time Complexity: O(m * n), where m is the length of str1 and n is the length of str2. This arises from filling out the DP table using nested loops.
  • Space Complexity: O(m * n) for the dp table.

Space Optimization

While the above approach is straightforward, it can be optimized to O(n) in space complexity by only keeping track of the current and previous rows of the DP table, as only the last row and the current row are needed at any point in time.

Summary

This dynamic programming approach efficiently computes the length of the longest common subsequence between two strings, balancing clarity and performance for practical input sizes.