Longest Common Subsequence: A Dynamic Programming Solution

The "Longest Common Subsequence" (LCS) problem is a well-known challenge in computer science. It involves finding the longest sequence of characters that appear in the same order in both of two given strings.

Problem Statement

Given two strings text1 and text2, find the length of their longest common subsequence. A subsequence is a sequence that appears in the same relative order in both strings but isn't necessarily contiguous.

Examples

• Input: text1 = "abcde", text2 = "ace" Output: 3 Explanation: The longest common subsequence is "ace" and its length is 3.

• Input: text1 = "abc", text2 = "abc" Output: 3 Explanation: The longest common subsequence is "abc" and its length is 3.

Dynamic Programming Solution

function longestCommonSubsequence(text1, text2) {
  let m = text1.length,
    n = text2.length;
  let dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (text1[i - 1] === text2[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[m][n];
}

Breaking Down the Solution

• Initialization: Create a 2D array dp with dimensions (len(text1) + 1) x (len(text2) + 1) and initialize all elements to 0.
• Dynamic Programming Iteration: Iterate over each character in text1 and text2. Update dp[i][j] with the length of the LCS up to that point.
• Character Match: If characters match (text1[i - 1] === text2[j - 1]), increment the length of the LCS by 1 from the previous characters' LCS length.
• Character Mismatch: If characters don't match, carry forward the maximum LCS length found so far.
• Return the LCS Length: The value in dp[m][n] gives the length of the LCS.

Conclusion

The LCS problem is a fundamental dynamic programming challenge, demonstrating how to break down a complex problem into smaller sub-problems. It's widely used in text comparison, DNA sequencing, and understanding the principles of building up solutions incrementally.