longest-common-subsequence.ts

/**
 * 1143. Longest Common Subsequence  (Medium)
 * Link: https://leetcode.com/problems/longest-common-subsequence/
 *
 * Return the length of the longest subsequence common to two strings. A
 * subsequence keeps relative order but need not be contiguous.
 *
 * Example:
 *   Input:  text1 = "abcde", text2 = "ace"
 *   Output: 3            // "ace"
 *
 * Approach:
 *   2-D DP. dp[i][j] = LCS length of the first i chars of text1 and first j of
 *   text2. If the current characters match, dp[i][j] = dp[i-1][j-1] + 1;
 *   otherwise the best of dropping one char from either side. We keep only the
 *   previous row to reduce space to O(n).
 *
 * Time:  O(m * n)
 * Space: O(n)
 */
export function longestCommonSubsequence(text1: string, text2: string): number {
  const m = text1.length;
  const n = text2.length;
  let prev = new Array<number>(n + 1).fill(0);

  for (let i = 1; i <= m; i++) {
    const curr = new Array<number>(n + 1).fill(0);
    for (let j = 1; j <= n; j++) {
      if (text1[i - 1] === text2[j - 1]) {
        curr[j] = prev[j - 1] + 1;
      } else {
        curr[j] = Math.max(prev[j], curr[j - 1]);
      }
    }
    prev = curr;
  }

  return prev[n];
}