1143. Longest Common Subsequence

1function longestCommonSubsequence(a: string, b: string): number {
2  const dp = new Array(b.length + 1).fill(0);
3  for (let i = 1; i <= a.length; i++) {
4    let diag = 0;
5    for (let j = 1; j <= b.length; j++) {
6      const up = dp[j];
7      dp[j] = a[i - 1] === b[j - 1] ? diag + 1 : Math.max(up, dp[j - 1]);
8      diag = up;
9    }
10  }
11  return dp[b.length];
12}

One row of zeros.

Space: play/pause · ←/→: step