M.A.T.R.I.X

Appearance

4.24.2 — Longest Common Subsequence ​

LeetCode 1143 · Medium · ★ Blind 75

The problem ​

Return the length of the longest subsequence common to both strings. A subsequence keeps order but may skip characters.

"abcde", "ace"   →  3     ("ace")
"abc",   "abc"   →  3
"abc",   "def"   →  0

The pattern ​

This is the template for every "compare two sequences" problem, so it is worth learning properly rather than memorising.

Whenever a problem involves two strings, make a grid: one axis per string. That single decision is the whole recognition step.

Let dp[i][j] be the LCS length of the first i characters of text1 and the first j of text2.

Now compare the two characters at the end of those prefixes. There are exactly two cases:

They match. That character can be the end of the common subsequence, so take it and shrink both:

dp[i][j] = 1 + dp[i-1][j-1]

They differ. They cannot both be the ending, so at least one of them is not used. Try dropping each and keep the better:

dp[i][j] = \max\big(dp[i-1][j],\ dp[i][j-1]\big)

Base case: dp[0][j] = dp[i][0] = 0. An empty string shares nothing.

Why "prefixes" and not "ending at". Using prefix lengths means the answer is dp[m][n] directly, and the empty prefixes give the base row and column for free.

The solution ​

python
class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m, n = len(text1), len(text2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]      # note: m+1 by n+1

        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if text1[i - 1] == text2[j - 1]:        # note the −1 offsets
                    dp[i][j] = 1 + dp[i - 1][j - 1]
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

        return dp[m][n]
ts
function longestCommonSubsequence(text1: string, text2: string): number {
  const m = text1.length, n = text2.length;
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (text1[i - 1] === text2[j - 1]) dp[i][j] = 1 + dp[i - 1][j - 1];
      else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
    }
  }

  return dp[m][n];
}

The (m+1) × (n+1) table and the −1 offsets go together. Row i means "the first i characters", so row 0 is the empty prefix and the character it just consumed is text1[i-1]. Sizing the table m × n instead forces a special case for the first row and column, and it is where most of the errors in this family come from.

Fill order: dp[i][j] reads [i-1][j-1], [i-1][j] and [i][j-1] — all smaller. Top to bottom, left to right.

Trace ​

"abcde" against "ace":

        ''  a  c  e
   ''    0  0  0  0
    a    0  1  1  1
    b    0  1  1  1
    c    0  1  2  2
    d    0  1  2  2
    e    0  1  2  3

Read the diagonal jumps: a matches at (1,1), c at (3,2), e at (5,3). The answer 3 is in the bottom-right corner.

Space optimisation ​

The recurrence only ever reads the previous row and the current one, so two rows suffice:

python
prev = [0] * (n + 1)
for i in range(1, m + 1):
    curr = [0] * (n + 1)
    for j in range(1, n + 1):
        if text1[i-1] == text2[j-1]:
            curr[j] = 1 + prev[j-1]
        else:
            curr[j] = max(prev[j], curr[j-1])
    prev = curr
return prev[n]

O(\min(m, n)) space if you also make the shorter string the inner axis.

But if you need the subsequence itself, keep the full table and walk backwards from dp[m][n]: a diagonal step means the character was matched, otherwise move towards the larger neighbour. Reconstruction always needs the table — the same trade as in 4.23.

Complexity ​

O(mn) time, O(mn) or O(n) space.

The family this template solves ​

Almost every two-string DP is this grid with the two cases rewritten:

problemmatch casemismatch case
LCS1 + dp[i-1][j-1]max(dp[i-1][j], dp[i][j-1])
Edit Distancedp[i-1][j-1]1 + min of three
Distinct Subsequencesdp[i-1][j-1] + dp[i-1][j]dp[i-1][j]
Longest Common Substring1 + dp[i-1][j-1]0 — must be contiguous
Shortest Common Supersequence1 + dp[i-1][j-1]1 + min(dp[i-1][j], dp[i][j-1])

Longest Common Substring differs by one cell: a mismatch resets to 0, because a substring must be contiguous. And the answer is the maximum over the table rather than the corner, since the best run may end anywhere.

Two other useful facts:

  • Longest Palindromic Subsequence of s = LCS of s and s reversed.
  • Minimum deletions to make two strings equal = m + n − 2 × LCS.

Where this goes next ​

  • Edit Distance — the same grid with three operations. 4.24.9.
  • Distinct Subsequences — counting instead of measuring. 4.24.8.
  • Interleaving String — two strings against a third. 4.24.6.
  • diff — the Unix tool is LCS on lines instead of characters. Git's diff is a tuned version of the same algorithm, which is a good thing to mention.

What the interviewer will push on ​

"Why a 2-D table?" Two sequences, one axis each. Say it as the recognition step.

"Derive the two cases." Characters match or they do not; if they differ, at least one is unused.

"Why is the table (m+1) × (n+1)?" The empty prefixes give the base row and column with no special case.

"Can you use O(n) space?" Two rows — but you lose the ability to reconstruct the subsequence.

"How do you get the subsequence itself?" Walk the full table backwards.

"What changes for the longest common substring?" A mismatch resets the cell to 0, and the answer is the table maximum.

One thing to volunteer: mention that this is what diff does. It turns an exercise into a tool you use every day, and it makes the problem memorable.

Next: 4.24.3 Best Time to Buy and Sell Stock with Cooldown — where the second dimension is not a position but a state.