Longest Common Subsequence — Memoized Recursion

The problem

Same LCS, cached: `lcsMemoized(stringA, stringB, lenA, lenB)` allocates a `(lenA + 1) x (lenB + 1)` grid of `null` and hands it to the same recursion, which now checks the grid before doing any work and writes to it before returning.

`"abcde"` and `"ace"` still return `3`. What changes is the call count: the plain recursion visits the pair `(3, 2)` down several different branches and re-solves it each time; here it's solved once and read back afterwards.

The approach

The key is exactly the set of parameters that vary between calls, which is `(lenA, lenB)` and nothing else. `stringA` and `stringB` are passed down untouched, so they're not part of the state and don't belong in the key — a mistake worth avoiding deliberately, because a cache keyed on more than the state still returns correct answers and just quietly stops hitting. Sizing the grid at `lenA + 1` by `lenB + 1` means the parameters index it directly with no offset arithmetic.

`!= null` is the right test and it's doing two things at once. Loose inequality against `null` catches both `null` and `undefined`, so an out-of-range read can't be mistaken for a cached `0`. More importantly it distinguishes 'not computed' from 'computed, answer is zero' — and `0` is a perfectly ordinary LCS length for strings that share no characters. A truthiness check would turn every one of those cells into a permanent cache miss, which is the specific bug that makes a memoized solution look correct in tests and time out on the disjoint-strings input.

The base case is checked before the lookup, which has a quiet consequence: row `0` and column `0` are never written, and stay `null` for the life of the call. The table is allocated at full size and its border is dead space. That's harmless — the `if` is cheaper than the lookup it replaces — but it's the reason the memoized grid and the tabulated grid from the next entry aren't identical objects even though they compute the same function.

The counting argument for the complexity is worth stating rather than asserting. There are `m * n` distinct states, each is computed at most once because the write happens before every return path, and each computation does constant work outside its recursive calls. So `O(m * n)` time, `O(m * n)` for the table, plus `O(m + n)` of stack because the deepest chain decrements one index at a time. The exponent didn't get smaller — the repeated subtrees stopped existing.

Mechanically this is the previous file plus three edits: a wrapper that allocates, a `memo` parameter threaded through, and two lines in the body. That is the entire top-down conversion for any DP whose state is already correctly identified — which is the actual reason to write the plain recursion first. If the memo key isn't obvious, the state wasn't settled, and no amount of caching will fix that.

The solution

export function lcsMemoized(stringA, stringB, lenA, lenB) {
  const memo = Array.from({ length: lenA + 1 }, () =>
    Array(lenB + 1).fill(null),
  );
  return lcsRecursionHelper(stringA, stringB, lenA, lenB, memo);
}

function lcsRecursionHelper(stringA, stringB, lenA, lenB, memo) {
  if (lenA === 0 || lenB === 0) {
    return 0;
  }

  if (memo[lenA][lenB] != null) {
    return memo[lenA][lenB];
  }

  if (stringA[lenA - 1] == stringB[lenB - 1]) {
    memo[lenA][lenB] =
      1 + lcsRecursionHelper(stringA, stringB, lenA - 1, lenB - 1, memo);
    return memo[lenA][lenB];
  }
  memo[lenA][lenB] = Math.max(
    lcsRecursionHelper(stringA, stringB, lenA - 1, lenB, memo),
    lcsRecursionHelper(stringA, stringB, lenA, lenB - 1, memo),
  );
  return memo[lenA][lenB];
}

Time O(m * n)Space O(m * n)