Medium#11438 min readDynamic Programming2D DPStringsLeetCode

Longest Common Subsequence

Match-or-skip 2D DP with 1D row collapse

The classic 2D string DP. Understand match vs. skip transitions.

Published Apr 17, 2026

Problem

Given two strings text1 and text2, return the length of their longest common subsequence (LCS). A subsequence keeps order but can drop characters. If there is none, return 0.

Input

Output

Explanation

The LCS is 'ace'.

Input

Output

Explanation

Equal strings share their entire length.

Input

Output

Explanation

No characters in common.

Intuition

Consider the last characters. There are exactly two cases:

They match: text1[i - 1] == text2[j - 1]. Then they both belong to an LCS, so dp[i][j] = 1 + dp[i - 1][j - 1].
They differ: at least one of them is not in the LCS. So either drop the last of text1 or drop the last of text2, whichever gives the longer LCS: dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]).

Base: dp[0][j] = dp[i][0] = 0 (empty strings share zero characters).

This "match-or-skip" template is the canonical 2D string DP. It's simple to derive, and once you recognize the shape you can write it in your sleep:

if s1[i-1] == s2[j-1]:
    dp[i][j] = 1 + dp[i-1][j-1]
else:
    dp[i][j] = max(dp[i-1][j], dp[i][j-1])

Like #62's grid DP, transitions only touch the row above and the cell to the left in the current row. Collapse to a 1D buffer: iterate j left-to-right, but cache the old dp[j - 1] from the row above before you overwrite it — that's the "diagonal" input the match branch needs.

Approach

2D Table

TimeO(m · n)

SpaceO(m · n)

Direct translation. Easy to print and debug, heaviest on memory. Use .as_bytes() in Rust to avoid panicking on Unicode boundaries; LC inputs are ASCII.

impl Solution {
    pub fn longest_common_subsequence(text1: String, text2: String) -> i32 {
        let a = text1.as_bytes();
        let b = text2.as_bytes();
        let m = a.len();
        let n = b.len();
        let mut dp = vec![vec![0i32; n + 1]; m + 1];
        for i in 1..=m {
            for j in 1..=n {
                dp[i][j] = if a[i - 1] == b[j - 1] {
                    dp[i - 1][j - 1] + 1
                } else {
                    dp[i - 1][j].max(dp[i][j - 1])
                };
            }
        }
        dp[m][n]
    }
}

Rust · runnable

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

TypeScript · runnable

1D Rolling Buffer

TimeO(m · n)

SpaceO(min(m, n))

Recommended

Iterate one string along the outer loop, the other along the inner. Before overwriting dp[j], save it in prev_diag — that's the value that will become dp[i - 1][j - 1] on the next iteration. A small amount of bookkeeping for a substantial memory win.

impl Solution {
    pub fn longest_common_subsequence(text1: String, text2: String) -> i32 {
        // Iterate over the shorter string on the inner axis.
        let (a, b) = if text1.len() < text2.len() {
            (text2.as_bytes(), text1.as_bytes())
        } else {
            (text1.as_bytes(), text2.as_bytes())
        };
        let n = b.len();
        let mut dp = vec![0i32; n + 1];
        for &ai in a {
            let mut prev_diag = 0;
            for j in 1..=n {
                let saved = dp[j];
                if ai == b[j - 1] {
                    dp[j] = prev_diag + 1;
                } else {
                    dp[j] = dp[j].max(dp[j - 1]);
                }
                prev_diag = saved;
            }
        }
        dp[n]
    }
}

Rust · runnable

function longestCommonSubsequence(text1: string, text2: string): number {
  // Iterate over the shorter string on the inner axis.
  const [a, b] = text1.length < text2.length ? [text2, text1] : [text1, text2];
  const n = b.length;
  const dp = new Array<number>(n + 1).fill(0);
  for (let i = 0; i < a.length; i++) {
    let prevDiag= 0;
    for (let j= 1; j <= n; j++) {
      const saved= dp[j];
      if (a[i]= b[j - 1]) {
        dp[j]= prevDiag + 1;
      } else {
        dp[j]= Math.max(dp[j], dp[j - 1]);
      }
      prevDiag= saved;
    }
  }
  return dp[n];
}

TypeScript · runnable

Trace

2D fill on text1 = "abcde", text2 = "ace":

i (text1[i-1])	j=1 'a'	j=2 'c'	j=3 'e'
1 'a'	1	1	1
2 'b'	1	1	1
3 'c'	1	2	2
4 'd'	1	2	2
5 'e'	1	2	3

Return dp[5][3] = 3. ✓ (The LCS is "ace".)

Edge cases

Either string empty — return 0. The base row/column of zeros handles this without a special case.
Equal strings — return the length. Every diagonal match adds one.
No common character — return 0. The match branch never fires; the max-of-neighbors propagates zero forward.
Huge inputs (LC caps at 1000 × 1000) — the 2D form uses ~4 MB; the 1D form uses ~4 KB. Prefer the 1D form when memory is tight.

💡

Tip

LCS (max, +1) and Edit Distance (min, +1) share this skeleton. If you see "compare two strings character-by-character with a match/mismatch decision," reach for the 2D table first, then collapse.

Takeaway

The match-or-skip 2D string DP is a template you'll use for the rest of your career. Every variant — LCS (#1143), Edit Distance (#72), Delete Operations (#583), Shortest Common Supersequence — is the same recurrence with a different aggregator.

The row-collapse trick you learned in #62 Unique Paths applies unchanged: transitions touch one cell above and one to the left, so a single row buffer (plus the diagonal cache) is enough. Pair that with a shorter-axis-inside iteration and you get O(m · n) time and O(min(m, n)) memory — the production form.