C# Coding Test Course, Finding the Longest Common Subsequence

Problem Description

Given two strings A and B, the task is to find the Longest Common Subsequence (LCS) of these strings. A subsequence is a sequence derived from another sequence where the order of characters is preserved, allowing for deletion. In other words, a subsequence of A must exist in B.

For example, if string A is “ABCBDAB” and B is “BDCAB”, then the longest common subsequence is “BCAB”. This LCS problem requires efficient algorithms across various fields.

Problem Input

The lengths N and M of the two strings A and B (1 ≤ N, M ≤ 1000) and the strings A and B are provided.

Problem Output

Output the length of the longest common subsequence.

Problem Solving Process

1. Understanding Dynamic Programming

This problem can be solved using Dynamic Programming (DP). DP is a technique to improve efficiency by breaking down complex problems into smaller subproblems. Here, a DP array is used to store and calculate the LCS lengths between each pair of characters.

2. Initializing the DP Array

First, initialize a two-dimensional DP array based on the lengths of the strings A and B. DP[i][j] represents the length of the longest common subsequence of the first i characters of A and the first j characters of B.

    int[,] dp = new int[N + 1, M + 1];
    

3. DP State Transition

The DP rules are as follows:

• If the i-th character of A and the j-th character of B are the same: dp[i][j] = dp[i - 1][j - 1] + 1
• If the i-th character of A and the j-th character of B are different: dp[i][j] = Math.Max(dp[i - 1][j], dp[i][j - 1])

4. Final Result

After populating the DP array, dp[N][M] will contain the length of the longest common subsequence.

Code Implementation

    using System;

    class Program
    {
        static void Main(string[] args)
        {
            string A = "ABCBDAB";
            string B = "BDCAB";
            int N = A.Length;
            int M = B.Length;

            int[,] dp = new int[N + 1, M + 1];

            for (int i = 1; i <= N; i++)
            {
                for (int j = 1; j <= M; j++)
                {
                    if (A[i - 1] == B[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]);
                    }
                }
            }

            Console.WriteLine("Length of the longest common subsequence: " + dp[N, M]);
        }
    }
    

Test Cases

Example Input

    A: ABCBDAB
    B: BDCAB
    

Example Output

    Length of the longest common subsequence: 4
    

Time Complexity Analysis

The time complexity of this dynamic programming algorithm is O(N * M), and the space complexity is also O(N * M). This ensures satisfactory performance even when the lengths of the two strings are 1000.

Conclusion

The Longest Common Subsequence (LCS) problem is a key problem that illustrates how to determine relationships in various fields of computer science. It has been confirmed that it can be solved efficiently using dynamic programming. This method frequently appears in coding tests, so it is important to understand it well and practice.