Day 5 - Challenge 2 - Longest Common Subsequence

Solving the Longest Common Subsequence Problem using JavaScript

Introduction

The Longest Common Subsequence (LCS) problem is a classic dynamic programming challenge that involves finding the length of the longest subsequence shared between two strings. In this blog post, we will delve into a step-by-step solution to this problem using a dynamic programming approach in JavaScript.

Dynamic Programming Approach

To solve the LCS problem efficiently, we will adopt a dynamic programming strategy. The core idea is to create a 2D table where each cell (i, j) represents the length of the LCS between the first i characters of the first string and the first j characters of the second string.

Let's break down the process of solving this problem:

1. Initialization: Create a 2D array dp of dimensions (m+1) x (n+1), where m and n are the lengths of the two input strings.

2. Iteration: Use nested loops to iterate over each character in the two strings. Let i denote the current index in the first string and j denote the current index in the second string.

3. Comparison: If the characters at indices i and j are the same, increment the value in dp[i+1][j+1] by 1 compared to dp[i][j]. This indicates that the current character is part of the LCS.

4. Updating Table: If the characters are not the same, set dp[i+1][j+1] to the maximum of dp[i][j+1] and dp[i+1][j]. This step considers the possibility that the current character is either part of the LCS or not.

5. Final Result: After completing the loops, the value at dp[m][n] represents the length of the longest common subsequence.

6. Return: Return the value at dp[m][n] as the answer to the problem.

JavaScript Implementation

Here's the JavaScript code that implements the dynamic programming approach to solve the Longest Common Subsequence problem:

function longestCommonSubsequence(text1, text2) {
    const m = text1.length;
    const n = text2.length;
    const dp = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0));

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (text1[i] === text2[j]) {
                dp[i + 1][j + 1] = dp[i][j] + 1;
            } else {
                dp[i + 1][j + 1] = Math.max(dp[i][j + 1], dp[i + 1][j]);
            }
        }
    }

    return dp[m][n];
}

const text1 = "abcdef";
const text2 = "acef";
console.log("Length of Longest Common Subsequence:", longestCommonSubsequence(text1, text2));

Demo

Longest Common Subsequence Demo

Conclusion

The dynamic programming approach is a powerful technique for solving the Longest Common Subsequence problem efficiently. By breaking down the problem into smaller subproblems and utilizing a table to store intermediate results, we can calculate the length of the longest subsequence shared between two strings. This approach has broad applications in various scenarios where sequence matching is essential.

Now write the same program in your favorite language in comment section. 

Other Challenges:

1. Day 2 Challenges
2. Day 3 Challenges
3. Day 4 Challenges