Longest Common Subsequence (LCS): A Classic 2D Dynamic Programming

The Longest Common Subsequence (LCS) of two strings is the longest sequence of characters that appears in both, in the same relative order but not necessarily contiguous. For "ABCBDAB" and "BDCAB", one LCS is "BCAB" (length 4). LCS is the foundational two-sequence DP — it underpins diff tools, version control, and DNA alignment. This page derives the 2D table and shows how to recover the actual subsequence.

Subsequence vs substring

A substring is contiguous ("BCB" from "ABCBDAB"). A subsequence only keeps order — you may delete characters but not reorder them ("ABD" is a subsequence of "ABCBDAB"). LCS deals with subsequences.

Defining the DP

Compare the two strings from their fronts (or backs). Look at the last characters of the first i of a and the first j of b:

State: dp[i][j] = length of the LCS of a[0..i-1] and b[0..j-1].
Transition:
- if a[i-1] == b[j-1]: they extend a common subsequence → dp[i][j] = 1 + dp[i-1][j-1].
- else: drop one character → dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
Base cases: dp[0][j] = dp[i][0] = 0 — an empty string shares nothing.

The answer is dp[m][n].

Tabulation: O(mn) time, O(mn) space

int lcs(const std::string& a, const std::string& b) {
    int m = a.size(), n = b.size();
    std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1, 0));
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            if (a[i - 1] == b[j - 1])
                dp[i][j] = 1 + dp[i - 1][j - 1];
            else
                dp[i][j] = std::max(dp[i - 1][j], dp[i][j - 1]);
    return dp[m][n];
}

int lcs(String a, String b) {
    int m = a.length(), n = b.length();
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            if (a.charAt(i - 1) == b.charAt(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];
}

function lcs(a, b) {
  const m = a.length, n = b.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 (a[i - 1] === b[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];
}

def lcs(a, b):
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if a[i - 1] == b[j - 1]:
                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]

Reconstructing the subsequence

The table holds the length; to recover the actual characters, walk backward from dp[m][n]. When characters match, that character is part of the LCS; otherwise step toward the larger neighbor.

std::string lcsString(const std::string& a, const std::string& b) {
    int m = a.size(), n = b.size();
    std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1, 0));
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            dp[i][j] = (a[i - 1] == b[j - 1]) ? dp[i - 1][j - 1] + 1
                                              : std::max(dp[i - 1][j], dp[i][j - 1]);
    std::string res;
    int i = m, j = n;
    while (i > 0 && j > 0) {
        if (a[i - 1] == b[j - 1]) { res += a[i - 1]; i--; j--; }
        else if (dp[i - 1][j] >= dp[i][j - 1]) i--;
        else j--;
    }
    std::reverse(res.begin(), res.end());
    return res;
}

String lcsString(String a, String b) {
    int m = a.length(), n = b.length();
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            dp[i][j] = (a.charAt(i - 1) == b.charAt(j - 1)) ? dp[i - 1][j - 1] + 1
                       : Math.max(dp[i - 1][j], dp[i][j - 1]);
    StringBuilder sb = new StringBuilder();
    int i = m, j = n;
    while (i > 0 && j > 0) {
        if (a.charAt(i - 1) == b.charAt(j - 1)) { sb.append(a.charAt(i - 1)); i--; j--; }
        else if (dp[i - 1][j] >= dp[i][j - 1]) i--;
        else j--;
    }
    return sb.reverse().toString();
}

function lcsString(a, b) {
  const m = a.length, n = b.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++)
      dp[i][j] = a[i - 1] === b[j - 1] ? dp[i - 1][j - 1] + 1
                 : Math.max(dp[i - 1][j], dp[i][j - 1]);
  let res = "", i = m, j = n;
  while (i > 0 && j > 0) {
    if (a[i - 1] === b[j - 1]) { res = a[i - 1] + res; i--; j--; }
    else if (dp[i - 1][j] >= dp[i][j - 1]) i--;
    else j--;
  }
  return res;
}

def lcs_string(a, b):
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            dp[i][j] = (dp[i - 1][j - 1] + 1 if a[i - 1] == b[j - 1]
                        else max(dp[i - 1][j], dp[i][j - 1]))
    res = []
    i, j = m, n
    while i > 0 and j > 0:
        if a[i - 1] == b[j - 1]:
            res.append(a[i - 1]); i -= 1; j -= 1
        elif dp[i - 1][j] >= dp[i][j - 1]:
            i -= 1
        else:
            j -= 1
    return "".join(reversed(res))

For beginners: If you only need the length, two rolling rows reduce space to O(n). But reconstructing the string requires the full table (or a clever divide-and-conquer), so keep the 2D grid when you need the characters back.

Complexity

Goal	Time	Space
LCS length	O(mn)	O(mn), or O(n) rolling
LCS string	O(mn)	O(mn)

Pitfall: Don’t confuse LCS with longest common substring (contiguous) — the substring version resets dp[i][j] to 0 on a mismatch and tracks the global max, not dp[m][n].

LCS is the springboard to edit distance and many subsequence DPs. Next up: Longest Increasing Subsequence.