1143. Longest Common Subsequence

Find the longest sequence of characters that appears in both strings in the same relative order (not necessarily contiguous). A classic 2D dynamic-programmingtable lets you build the answer in O(m × n) with a single elegant recurrence: match → diagonal + 1, no-match → max of up or left.

● Medium2D DPTypeScript

PROBLEM What we're solving

Given two strings, return the length of their longest common subsequence (LCS) — a subsequence that appears in both strings in the same relative order, but not necessarily contiguously. text1="abcde", text2="ace" → 3 (the subsequence "ace"appears in both). text1="abc", text2="abc" → 3. text1="abc", text2="def" → 0.

KEY IDEA Build the answer character-by-character in a table

Insight → define dp[i][j] as the LCS length of text1[0..i-1] and text2[0..j-1]. The recurrence has only two cases:

Characters match: dp[i][j] = dp[i-1][j-1] + 1 — the LCS extends diagonally.
No match: dp[i][j] = max(dp[i-1][j], dp[i][j-1]) — skip one character from either string, take the better result.

Every subproblem depends only on previously-filled cells, so we fill row-by-row, left-to-right.

RECURRENCE Step-by-step recipe

0 · Allocate table. Create an (m+1)×(n+1) table, all zeros. The extra row and column represent the empty-string base cases: LCS with an empty string is 0.
1 · Iterate i from 1→m, j from 1→n. For each cell, compare text1[i-1] and text2[j-1].
2a · Match. dp[i][j] = dp[i-1][j-1] + 1. The diagonal inherits the best LCS of both shorter prefixes, plus this shared character.
2b · No match. dp[i][j] = max(dp[i-1][j], dp[i][j-1]). We can only skip one character; take the skip that left the longer LCS.
3 · Answer. dp[m][n] is the final result. Backtrace diagonally whenever a match drove the value to recover the actual subsequence.

Classic confusion → people conflate LCS (subsequence — gaps allowed) with Longest Common Substring (contiguous — no gaps). For substring the recurrence resets on mismatch (dp[i][j] = 0 instead of max(up,left)); the answer is the table maximum, not the corner cell.

Pattern transfer → the same 2D DP skeleton underlies Edit Distance (add cost to the no-match case), Shortest Common Supersequence (derive from LCS table), Longest Palindromic Subsequence (LCS of string with its reverse), and Distinct Subsequences.

COST Complexity & space optimisation

Recursive without memo

O(2ⁿ)

Recomputes every overlapping subproblem.

2D DP table

O(m·n)

O(m·n) time; O(m·n) space (or O(n) with rolling row).

Space optimisation

Because each row only looks at the row above, you can keep two 1-D arrays — prev and curr— cutting space from O(m × n) to O(n). A single-array version is also possible with a diagonal save variable. Note: you lose backtrace ability with rolling rows.

RUN IT Fill the DP table, then trace the LCS

text1 =text2 =

step 0 / 37

STARTAllocate a 6×4 table. dp[i][j] = length of the LCS of the first i chars of “abcde” and the first jchars of “ace”. Base cases (row 0 and col 0) are already 0.

1▶function longestCommonSubsequence(text1: string, text2: string): number {
2▶  const m = text1.length;
3▶  const n = text2.length;
4▶  // dp[i][j] = LCS length of text1[0..i-1] and text2[0..j-1]
5▶  const dp: number[][] = Array.from({ length: m + 1 }, () => new Array<number>(n + 1).fill(0));
6 
7  for (let i = 1; i <= m; i++) {
8    for (let j = 1; j <= n; j++) {
9      if (text1[i - 1] === text2[j - 1]) {
10        dp[i][j] = dp[i - 1][j - 1] + 1;   // match: extend diagonal
11      } else {
12        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); // no match: best of up/left
13      }
14    }
15  }
16  return dp[m][n];
17}

Loop indices

i: —

j: —

Source values

—

Current comparison

waiting…

LCS result

revealed at end

current cellsource cellschosen sourceLCS path

slowfast

TYPESCRIPT The solution, annotated

longestCommonSubsequence.ts
function longestCommonSubsequence(text1: string, text2: string): number {
  const m = text1.length;
  const n = text2.length;
  // dp[i][j] = LCS length of text1[0..i-1] and text2[0..j-1]
  const dp: number[][] = Array.from({ length: m + 1 }, () => new Array<number>(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] = dp[i - 1][j - 1] + 1;   // match: extend diagonal
      } else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); // no match: best of up/left
      }
    }
  }
  return dp[m][n];
}

Reading it block by block

Lines 4–5 — allocate. We build an (m+1)×(n+1) table filled with zeros. Row 0 and column 0 model the empty-prefix base cases: LCS of any string with the empty string is 0.

Lines 7–8 — nested iteration. We process every pair of prefixes in row-major order. Because dp[i][j]only reads cells above and to the left, they're already filled when we need them.

Line 9–10 — match branch. When text1[i-1] === text2[j-1] the two characters can extend the LCS of the two shorter prefixes. We inherit the diagonal value and add 1.

Lines 11–12 — no-match branch. We can skip one character from either side. Takingmax(dp[i-1][j], dp[i][j-1]) picks the skip that preserves the longest LCS found so far.

Line 15 — answer. The bottom-right corner dp[m][n]is the LCS length of the full strings. To recover the actual subsequence, backtrace: whenever the match branch drove a cell's value, step diagonally and record that character.

Complexity → O(m × n) time (all cells visited once); O(m × n) space for the full table, reducible to O(n) with a rolling two-row approach.

INTERVIEWFollow-ups they'll ask

“Print the actual LCS, not just its length?” Backtrace from dp[m][n]: whenever text1[i-1] === text2[j-1] drove the value, prepend that char and step diagonally; otherwise move toward the larger neighbour.
“Reduce space to O(n)?” Keep two rows — prev and curr — swapping each iteration. A single-array solution uses a diag temp variable.
“How does this relate to Edit Distance?”Edit Distance adds a cost of 1 to the no-match case and tracks insert/delete/replace; LCS is the “free skip” version.
“Longest Palindromic Subsequence?” LCS of text1 with its reverse — same code, different inputs.
“Distinct Subsequences?” A counting variant of the same 2D table: instead of max, sum the ways; match adds the diagonal count.

OPTIMAL 2D DP

longestCommonSubsequence.ts
function longestCommonSubsequence(text1: string, text2: string): number {
  const m = text1.length;
  const n = text2.length;
  // dp[i][j] = LCS length of text1[0..i-1] and text2[0..j-1]
  const dp: number[][] = Array.from({ length: m + 1 }, () => new Array<number>(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] = dp[i - 1][j - 1] + 1;   // match: extend diagonal
      } else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); // no match: best of up/left
      }
    }
  }
  return dp[m][n];
}

Complexity → O(m × n) time (all cells visited once); O(m × n) space for the full table, reducible to O(n) with a rolling two-row approach.

ALT 1 Brute force — plain recursion, no memo

O(2^(m+n)) time · O(m+n) stack

Compare the two strings from the front: if the first characters match, count 1 plus the LCS of the rests; otherwise try dropping the first character of each side and take the better.

approach-2.ts
function longestCommonSubsequence(text1: string, text2: string): number {
  // i, j = how many characters of each string are still "in play".
  function lcs(i: number, j: number): number {
    if (i === text1.length || j === text2.length) return 0;

    if (text1[i] === text2[j]) {
      return 1 + lcs(i + 1, j + 1);          // match — consume both
    }
    return Math.max(lcs(i + 1, j), lcs(i, j + 1)); // skip one side or the other
  }

  return lcs(0, 0);
}

Note → The recurrence is right, but with no cache the same (i, j) pair is recomputed across countless branches, so the work is exponential. Memoizing on (i, j)— or filling the equivalent O(m·n)table bottom-up — is the fix.

MNEMONIC The one-liner

"Match → diagonal + 1; no-match → max(up, left). The corner is the answer."

TRIGGERS When you see _ → reach for _

"longest common subsequence / LCS"	2D DP table, m×n
two strings, order matters, gaps allowed	dp[i][j] = diagonal or max(up,left)
backtrace for actual subsequence	follow diagonal on matches from dp[m][n]
palindromic subsequence / supersequence	LCS of string with reverse / derived from LCS

SKELETON The reusable shape

skeleton.ts
function longestCommonSubsequence(text1: string, text2: string): number {
  const m = text1.length, n = text2.length;
  const dp = Array.from({ length: m + 1 }, () => new Array<number>(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] = dp[i - 1][j - 1] + 1;
      } else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }
  return dp[m][n];
}

FLASHCARDS Tap to flip

What does dp[i][j] represent in the LCS table?

The length of the LCS of text1[0..i-1] and text2[0..j-1].

tap to flip

1 / 7

Answer to reveal explanations. No penalty for retries.Score: 0 / 9

QUESTION 01

What is dp[i][j] when text1[i-1] === text2[j-1]?

QUESTION 02

For text1="abcde", text2="ace", the LCS length is:

QUESTION 03

Time complexity of the 2D DP approach?

QUESTION 04

What distinguishes LCS (longest common subsequence) from Longest Common Substring?

QUESTION 05

Which cells does dp[i][j] depend on when there is no match?

QUESTION 06

To reduce space from O(m·n) to O(n) you:

QUESTION 07

Which problem is directly solvable by calling LCS on a string and its reverse?

QUESTION 08

#1143 · Longest Common SubsequenceFind the longest sequence of characters present in both strings in the same order. A classic 2D DP table solves it in O(m×n): match → diagonal + 1, no-match → max(up, left).Which algorithmic approach does this primarily use?

QUESTION 09

PROBLEM What we're solving

KEY IDEA Build the answer character-by-character in a table

RECURRENCE Step-by-step recipe

COST Complexity & space optimisation

Space optimisation

RUN IT Fill the DP table, then trace the LCS

TYPESCRIPT The solution, annotated

Reading it block by block

INTERVIEWFollow-ups they'll ask

OPTIMAL 2D DP

ALT 1 Brute force — plain recursion, no memo

MNEMONIC The one-liner

TRIGGERS When you see ___ → reach for ___

SKELETON The reusable shape

FLASHCARDS Tap to flip

TRIGGERS When you see _ → reach for _