#1143 - Longest Common Subsequence

MediumDP - Multidimensional

Given two strings text1 and text2, return the length of their longest common subsequence (LCS). A subsequence is derived by deleting some (or no) characters without changing the order.

Input	Output
text1 = "abcde", text2 = "ace"	3 (LCS = "ace")
text1 = "abc", text2 = "abc"	3
text1 = "abc", text2 = "def"	0

Solution Space

Try it

/**
 * Returns the length of the longest common subsequence.
 *
 * dp[i][j] = LCS length of text1[0..i) and text2[0..j).
 *   - If chars match: dp[i-1][j-1] + 1
 *   - Else: max(dp[i-1][j], dp[i][j-1])
 *
 * @param text1 First string
 * @param text2 Second string
 * @returns Length of the LCS
 */
export function longestCommonSubsequence(text1: string, text2: string): number {
  const m = text1.length;
  const n = text2.length;
  const dp: number[][] = 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];
}

Approach: 2D DP – classic LCS recurrence. Match → diagonal + 1; mismatch → max of top or left.

Time: O(m · n) – fill the entire table.

Space: O(m · n) – the DP table.

Alternative approaches:

Approach	Idea	Time	Space
Space-optimized 1D DP	Only keep two rows (current and previous) since dp[i] depends only on dp[i-1]	O(m · n)	O(min(m, n))

Why the 2D approach is preferred: easier to understand and debug; the 1D optimization is straightforward to apply once correctness is verified.

#714 Best Time to Buy and Sell Stock with Transaction Fee

#136 Single Number