Longest Common Substring

The problem

Implement `lcsubstring(stringA, stringB, lenA, lenB)`: return the length of the longest *contiguous* string present in both inputs. Unlike a subsequence, a substring can't skip characters — it has to be an unbroken run in both strings.

`"abcde"` and `"abfce"` return `2` — the run `ab`. The subsequence version of the same pair returns `4` (`abce`), and the gap between those two numbers is the entire difference between the problems: subsequences get to jump the `f`, substrings don't.

The name is one character off from `lcs` and entirely lowercase, so `lcsubstring` and `lcsTopDown` sit next to each other in an import list looking almost identical. That's a call-site hazard rather than a bug, and the two functions answer different questions with the same signature.

The approach

The state redefinition is the whole entry, and it's easy to skim past because the code barely moves. `memo[i][j]` is now the length of the longest common *suffix* of the first `i` characters of A and the first `j` characters of B — the run that ends exactly at `stringA[i-1]` and `stringB[j-1]`. Anchoring the run to a fixed end position is what enforces contiguity: a run can only be extended if the characters immediately before it also matched, and `memo[i-1][j-1]` is precisely that question.

Which is why a mismatch writes `0` rather than inheriting anything. In the subsequence table, `memo[i][j]` was a best-so-far and a mismatch could fall back on `Math.max(memo[i][j-1], memo[i-1][j])` — answers computed elsewhere were still valid answers. Here there is nothing to inherit, because the cell is not a claim about the prefixes in general, it's a fact about position `(i, j)`. If the characters at that position differ, no run ends there, and the length of no run is zero.

That local meaning also breaks the usual habit of reading the answer off the corner. `memo[lenA][lenB]` now only reports whether the two strings happen to end with a common run — for `"abcde"` and `"abfce"` it's `1`, and the real answer is sitting in the middle of the grid. So `maxLength` tracks the largest value at the moment it's written. Doing it inside the fill costs nothing; the alternative is a second `O(m * n)` scan over a table you've already visited every cell of.

The match branch is byte-for-byte identical to the subsequence version — `memo[i][j] = 1 + memo[i-1][j-1]` — and it means something different. Same line, same lookup, different problem, because the definition of the cell it reads has changed underneath it. This is the argument against learning DP as a catalogue of recurrences: the recurrence is the smaller half of the idea, and copying it without the state definition is how you end up with a table that computes something nobody asked for.

Recovering the actual substring is cheaper here than it is for subsequences, and that's a real asymmetry. Store the `i` at which `maxLength` was last updated and the answer is `stringA.slice(i - maxLength, i)` — two extra lines, no table walk. Because reconstruction needs one index rather than a path, the `O(min(m, n))` two-row space optimisation loses nothing, whereas the same optimisation on the subsequence table throws away the ability to rebuild the answer at all.

The solution

export function lcsubstring(stringA, stringB, lenA, lenB) {
  // initialize the first row with 0
  const memo = Array.from({ length: lenA + 1 }, () =>
    Array(lenB + 1).fill(null),
  );
  let maxLength = 0;

  // initialize the first row with 0
  for (let i = 0; i <= lenA; i++) {
    memo[i][0] = 0;
  }

  // initialize the first column with 0
  for (let j = 0; j <= lenB; j++) {
    memo[0][j] = 0;
  }

  // implementation
  for (let i = 1; i <= lenA; i++) {
    for (let j = 1; j <= lenB; j++) {
      if (stringA[i - 1] == stringB[j - 1]) {
        memo[i][j] = 1 + memo[i - 1][j - 1];
        maxLength = Math.max(maxLength, memo[i][j]);
      } else {
        memo[i][j] = 0;
      }
    }
  }

  return maxLength;
}

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