JavaScript Coding Test Course, Longest Common Subsequence

Problem Description

Given two strings, the problem is to find the Longest Common Subsequence (LCS) of these two strings.
The longest common subsequence refers to the maximum length of the substring that overlaps while maintaining the order of the two strings.
For example, if string A is “ABCBDAB” and string B is “BDCAB”, the longest common subsequence can be “BDAB” or “BCAB”, etc.

Input Format

– The first line contains the length N of string A and the length M of string B. (1 ≤ N, M ≤ 1000)
– The second line contains string A.
– The third line contains string B.

Output Format

– Output the length of the longest common subsequence of the two strings.

Example

            Input:
            7 5
            ABCBDAB
            BDCAB

            Output:
            4
        

Approach to Solve the Problem

This problem is a typical example of Dynamic Programming.
To find the LCS, we compare the two strings to find matching characters,
solving the subproblems at that point to derive the final length.

Step-by-Step Approach

1. Initialize the Dynamic Programming Table:

   Create a 2D array DP. DP[i][j] stores the length of the longest common subsequence
   of the first i characters of string A and the first j characters of string B. The size of the array is (N+1) x (M+1).

2. Fill the Table:

   If the i-th character of A and the j-th character of B are the same, then DP[i][j] = DP[i-1][j-1] + 1.
   Otherwise, set DP[i][j] = max(DP[i-1][j], DP[i][j-1]).

3. Output the Result:

   By reaching DP[N][M], we can return the length of the longest common subsequence.

JavaScript Code

function longestCommonSubsequence(A, B) {
    const N = A.length;
    const M = B.length;
    
    // Initialize the DP table
    const DP = Array.from(Array(N + 1), () => Array(M + 1).fill(0));
    
    // Fill the DP table
    for (let i = 1; i <= N; i++) {
        for (let 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]);
            }
        }
    }
    
    return DP[N][M];
}

// Run the input example
const A = 'ABCBDAB';
const B = 'BDCAB';
console.log(longestCommonSubsequence(A, B)); // Output: 4
        

Review and Practice Problems

If you have fully understood this problem, try to enhance your skills with additional practice problems. Challenge yourself with the following problems:

• A problem to find the longest common subsequence among three given strings instead of two.
• A problem to find the longest common subsequence without distinguishing between uppercase and lowercase letters.
• A problem to output all possible combinations that derive the longest common subsequence.

Conclusion

The longest common subsequence problem is one of the important concepts in computer science and can be applied to various algorithm problems.
Solving this problem using Dynamic Programming will help tackle more complex problems. Practice by solving various problems!