Longest Common Subsequence in TypeScript: Keep the Prefixes

The awkward word in Longest Common Subsequence is "subsequence". We can skip characters, but we cannot shuffle them. That makes the problem different from finding a shared substring, and different again from counting letters that happen to occur in both strings. With "ab" and "ba", both letters are present, but the answer is one. Their order refuses to cooperate.
I find this problem easier once I stop trying to pick the matching characters immediately. Instead, I ask what we already know about shorter prefixes. That gives us a table whose meaning stays stable throughout the calculation. Only after that explanation works will I squeeze it into a single row.
One Answer for Every Pair of Prefixes
LeetCode's Longest Common Subsequence problem asks for a length, rather than the subsequence itself. Each input contains between one and 1,000 lowercase English letters. For "abcde" and "ace", the answer is three: we can retain a, c, and e in both strings without changing their order.
Let lengths[i][j] mean the longest common subsequence length between the first i characters of the first string and the first j characters of the second. The indices count characters already included in each prefix. They are not the indices of the last characters, which are i - 1 and j - 1.
The empty‑prefix row and column contain zero. If either side has no characters, there is nothing to match. Those extra cells also let the main loop use the same rule at every position, without a collection of special cases around the top and left edges.
There is a useful connection with my Unique Paths explanation: a cell summarises a smaller problem, and neighbouring cells supply its dependencies. The meaning of the stored number is different, so the transition must be different too.
Match the Final Characters, or Leave One Out
If the final characters match, we can extend a common subsequence of the two shorter prefixes by that character. The value is lengths[i - 1][j - 1] + 1. Matching the two final positions is safe: an optimal common subsequence can be chosen to end there, leaving its earlier characters inside the shorter prefixes.
If the characters differ, they cannot both form the final matched pair. We consider dropping the final character from either prefix and keep the larger answer: Math.max(lengths[i - 1][j], lengths[i][j - 1]). Taking the maximum matters. Adding those answers would count incompatible choices as though they could be joined together.
A direct recursive version can branch into both smaller problems repeatedly. Many branches arrive at the same pair of prefix lengths. Memoising that pair avoids repeated work; filling the table does the same reuse in an explicit dependency order, without recursive calls.
Here is the complete table version. Each row is allocated separately; filling an outer array with one shared inner array would make updates leak across rows.
export const longestCommonSubsequenceTable = (
first: string,
second: string
): number => {
const lengths = Array.from(
{ length: first.length + 1 },
() => new Array<number>(second.length + 1).fill(0)
);
for (let row = 1; row <= first.length; row += 1) {
for (let column = 1; column <= second.length; column += 1) {
lengths[row][column] = first[row - 1] === second[column - 1]
? lengths[row - 1][column - 1] + 1
: Math.max(lengths[row - 1][column], lengths[row][column - 1]);
}
}
return lengths[first.length][second.length];
};Read a Small Table Before Compressing It
For "abc" and "ac", the completed table looks like this. Each label names a whole prefix, including the empty one.
| First prefix | Empty | a | ac |
|---|---|---|---|
| Empty | 0 | 0 | 0 |
| a | 0 | 1 | 1 |
| ab | 0 | 1 | 1 |
| abc | 0 | 1 | 2 |
At the ab/ac cell, b and c differ. The answer stays one, taken from the cell above or the cell to the left. At abc/ac, the final c characters match. We take the earlier ab/a answer of one and extend it to two.
Notice what never appears in that calculation: a greedy decision to keep the earliest available letter and discard every alternative. The table preserves the best length for each pair of prefixes. It does not need to commit to a particular subsequence in order to calculate the final length.
A Rolling Row Needs Three Different Values
Every update reads the old row above it, the current row to its left, and the old diagonal. We therefore need only one array, provided we keep the diagonal before overwriting it. The shorter string supplies the columns, reducing the array's size.
export const longestCommonSubsequence = (
first: string,
second: string
): number => {
const rows = first.length >= second.length ? first : second;
const columns = first.length >= second.length ? second : first;
const lengths = new Array<number>(columns.length + 1).fill(0);
for (let row = 1; row <= rows.length; row += 1) {
let diagonal = 0;
for (let column = 1; column <= columns.length; column += 1) {
const above = lengths[column];
lengths[column] = rows[row - 1] === columns[column - 1]
? diagonal + 1
: Math.max(above, lengths[column - 1]);
diagonal = above;
}
}
return lengths[columns.length];
};Just before an update, lengths[column] still belongs to the previous row. I save it as above. The cell at lengths[column - 1] already belongs to the current row because we scan left to right. Finally, diagonal holds the previous row's preceding cell.
After writing the answer, assigning diagonal = above preserves the old value for the next column. Resetting the diagonal to zero at the start of each row represents the empty second prefix. Neither assignment is bookkeeping we can casually rearrange.
For example, using the newly updated left value instead of the old diagonal can give two matches for "ab" and "aa". There is only one matching a available in the first string. The optimisation has accidentally allowed it to be used twice. This is why I keep the table version beside the smaller one: it makes the overwritten information visible.
Costs, Character Handling, and the Missing Subsequence
For input lengths m and n, both versions take O(mn) time under constant‑cost character indexing and numeric operations. The table uses O(mn) auxiliary space; the rolling version uses O(min(m, n)). The maximum official dimensions produce one million inner‑loop updates. That describes the work, rather than promising a particular running time on every JavaScript engine.
These implementations index UTF-16 code units. That agrees with the challenge's lowercase English letters. General Unicode text would require an explicit choice about code points or user‑perceived characters, consistent tokenisation, and lengths measured in those tokens. Changing only one loop to for...of would not settle that question.
The answer is a number. Recovering an actual subsequence needs more work: with the complete table, we can walk backwards through matching and skipped positions. Ties can give several valid answers. The rolling row discards the history that straightforward backtracking needs, so I would keep the table if returning a sequence were the requirement.
This also distinguishes the problem from my Longest Increasing Subsequence article. That problem orders values inside one sequence; this one preserves positions across two sequences. Similar names are not a reason to reuse the same state.
Checking the Dependency Order
I checked both snippets against an independent oracle that enumerates subsequences of the shorter input and scans the other input for each candidate. It is deliberately impractical for long strings, but it does not repeat the table recurrence. The checks cover every pair of binary strings up to length six, seeded cases, repeated letters, mismatched order, and the maximum official dimensions with known answers.
Empty‑string checks are included as an extension: the functions return zero, although LeetCode's inputs are nonempty. I also keep the "ab"/"aa" regression because it catches a very plausible rolling‑row mistake that the friendly "abcde" example can conceal.
My Dynamic Programming Comparison Lab contains both implementations, the independent checks, and a failing dependency‑order example you can inspect. The useful exercise is to predict which old cell a variable represents before changing the loop, then let the small counterexample challenge that prediction.
Wrapping Up
The table works because each cell answers one precise prefix question. The rolling row works because it preserves the same dependencies whilst overwriting storage. I would explain those two facts before trying to remember the final loop. The saved diagonal then has a job, rather than looking like a spare variable that somehow makes the tests pass.