Longest Common Subsequence

📌 Definition:

Find the length of the longest subsequence common to two strings (characters in order but not necessarily contiguous; e.g. "abcde" and "ace" -> 3).

📖 Detailed Explanation:

A 2D DP where dp[i][j] is the LCS length of the first i characters of a and first j of b. If the characters match, dp[i][j] = dp[i-1][j-1] + 1; otherwise dp[i][j] = max(dp[i-1][j], dp[i][j-1]). O(m * n) time and space (reducible to O(min(m,n)) space).

💻 Solutions:

public static int lcs(String a, String b) {
    int[][] dp = new int[a.length() + 1][b.length() + 1];
    for (int i = 1; i <= a.length(); i++)
        for (int j = 1; j <= b.length(); j++)
            dp[i][j] = a.charAt(i - 1) == b.charAt(j - 1)
                ? dp[i - 1][j - 1] + 1
                : Math.max(dp[i - 1][j], dp[i][j - 1]);
    return dp[a.length()][b.length()];
}

function lcs(a, b) {
  const dp = Array.from({ length: a.length + 1 }, () => new Array(b.length + 1).fill(0));
  for (let i = 1; i <= a.length; i++)
    for (let j = 1; j <= b.length; j++)
      dp[i][j] = a[i - 1] === b[j - 1]
        ? dp[i - 1][j - 1] + 1
        : Math.max(dp[i - 1][j], dp[i][j - 1]);
  return dp[a.length][b.length];
}

def lcs(a, b):
    dp = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
    for i in range(1, len(a) + 1):
        for j in range(1, len(b) + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[len(a)][len(b)]

🔑 Key Points:

Subsequence keeps order, allows gaps
Match: dp[i-1][j-1] + 1; else max of dropping one char
O(m*n) time, O(m*n) space (reducible)
Different from longest common SUBSTRING

🌍 Real-World Example:

LCS is the engine behind diff tools, version-control merges, and DNA-sequence alignment — the classic two-sequence DP.

🎯 Scenario-Based Interview Question:

A candidate confuses this with longest common SUBSTRING. What is the difference in the recurrence?

‹ Previous

Coin Change — Minimum Coins

Next ›

Generate All Subsets (Power Set)