Longest Common Subsequence

Say you have two words. You want to know how similar they are. Not equal, just similar. How many characters do they share, in the same order? That question shows up everywhere. Spell checkers use it. The git diff you see on GitHub uses it. Even DNA matching uses it. The tool for it is called the Longest Common Subsequence, or LCS for short. So let us learn it step by step.

📚 What Is a Subsequence?

First we need one word clear. The whole problem depends on it. A subsequence is what you get when you take a string and delete some characters but keep the rest in the same order.

You are allowed to skip characters. You are not allowed to reorder them.

So take the word ABCDE. Here are some valid subsequences:

• ACE — we kept A, C, E and dropped the rest
• ABE — we kept A, B, E
• ABCDE — we kept everything (the full string counts too)
• "" — the empty string counts as well

But ECA is not a subsequence of ABCDE. The order is wrong. In ABCDE the A comes first. In ECA it comes last. Order matters.

People mix this up with substring. So let us clear that now.

So a substring is strict. The characters sit together. A subsequence is relaxed. It allows gaps. Every substring is also a subsequence, but not the other way around.

🎯 The LCS Problem

Now the real problem. You are given two strings. You want the longest subsequence that appears in both of them.

Take these two:

• X = "ABCBDAB"
• Y = "BDCAB"

One common subsequence is BCAB. Check it. B, C, A, B all appear in X in that order. They all appear in Y in that order too. Its length is 4. There is no common subsequence longer than that here. So the LCS length is 4.

For now we only ask for the length of the LCS, not the actual string. The length is what most problems want. And finding the length first makes the rest easy.

🧠 Why Brute Force Is Too Slow

The naive idea is to list every subsequence of the first string and check each one against the second. The trouble is that a string of length n has 2^n subsequences. For a string of just 40 characters that is over a trillion checks. Way too slow.

So we use dynamic programming. Dynamic programming means we break the big problem into small overlapping pieces. We solve each small piece once. Then we store the answer in a table so we never redo work.

🔑 The Match / No-Match Rule

Here is the idea that makes LCS click. We compare the two strings one character at a time, from the end. At each step we look at the last character of each piece.

Let i be how many characters of X we are looking at, and j how many of Y. We build a table where each cell dp[i][j] holds the LCS length of the first i characters of X and the first j characters of Y. The rules are short:

• If the two current characters match, that character is part of the LCS. So we take the answer from the smaller problem and add 1: dp[i][j] = dp[i-1][j-1] + 1.
• If they do not match, we cannot use both. So we drop one character, try both ways, and keep the better one: dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
• If either string is empty (i is 0 or j is 0), the LCS is 0. This is the base case and it fills the first row and first column with zeros.

That is the whole algorithm. Match means add one and go diagonal. No match means take the best of up or left.

📊 A Small Worked Example

Let us fill the table for X = "AGGT" and Y = "GT". The rows are characters of X. The columns are characters of Y. The extra empty row and column at the top hold the base-case zeros.

Read the bottom-right cell. It says 2. So the LCS of AGGT and GT has length 2, and that subsequence is GT. See how the G row first hit 1 because G matches G. Then the T row hit 2 because T matches T after that. The answer always sits in the last cell.

This diagram shows where each cell pulls its value from:

📝 Steps to Find the LCS Length

Let us turn the rules into a clear plan before we write any code.

1. Read both strings. Let m be the length of the first and n be the length of the second.
2. Make a table dp with m + 1 rows and n + 1 columns. Fill it with zeros. The extra row and column are the empty-string base case.
3. Loop i from 1 to m. Inside it, loop j from 1 to n.
4. If the character at i-1 in the first string equals the character at j-1 in the second, set dp[i][j] = dp[i-1][j-1] + 1.
5. Otherwise set dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
6. After both loops finish, the answer is in dp[m][n]. That is the LCS length.

💻 LCS in Five Languages

Now the code. Each one builds the same table and prints the LCS length for X = "ABCBDAB" and Y = "BDCAB", which we said is 4.

#include <stdio.h>
#include <string.h>

// returns the bigger of two numbers
int max(int a, int b) {
    return a > b ? a : b;
}

// builds the dp table and returns the LCS length
int lcs(const char *x, const char *y) {
    int m = strlen(x);
    int n = strlen(y);
    int dp[m + 1][n + 1];

    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (i == 0 || j == 0) {
                dp[i][j] = 0;                       // empty string base case
            } else if (x[i - 1] == y[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;    // characters match
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); // no match
            }
        }
    }
    return dp[m][n];
}

int main(void) {
    const char *x = "ABCBDAB";
    const char *y = "BDCAB";
    printf("LCS length: %d\n", lcs(x, y));
    return 0;
}

LCS length: 4

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

// builds the dp table and returns the LCS length
int lcs(const string &x, const string &y) {
    int m = x.size();
    int n = y.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (x[i - 1] == y[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;            // characters match
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); // no match
            }
        }
    }
    return dp[m][n];
}

int main() {
    string x = "ABCBDAB";
    string y = "BDCAB";
    cout << "LCS length: " << lcs(x, y) << endl;
    return 0;
}

LCS length: 4

public class Lcs {

    // builds the dp table and returns the LCS length
    static int lcs(String x, String y) {
        int m = x.length();
        int n = y.length();
        int[][] dp = new int[m + 1][n + 1];

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (x.charAt(i - 1) == y.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;                 // characters match
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); // no match
                }
            }
        }
        return dp[m][n];
    }

    public static void main(String[] args) {
        String x = "ABCBDAB";
        String y = "BDCAB";
        System.out.println("LCS length: " + lcs(x, y));
    }
}

LCS length: 4

# builds the dp table and returns the LCS length
def lcs(x, y):
    m = len(x)
    n = len(y)
    # table of zeros with one extra row and column for the base case
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if x[i - 1] == y[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1        # characters match
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])  # no match

    return dp[m][n]


x = "ABCBDAB"
y = "BDCAB"
print("LCS length:", lcs(x, y))

LCS length: 4

// builds the dp table and returns the LCS length
function lcs(x, y) {
  const m = x.length;
  const n = y.length;
  // table of zeros with one extra row and column for the base case
  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 (x[i - 1] === y[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1; // characters match
      } else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); // no match
      }
    }
  }
  return dp[m][n];
}

const x = "ABCBDAB";
const y = "BDCAB";
console.log("LCS length:", lcs(x, y));

LCS length: 4

⏱️ Time and Space Complexity

The work is one pair of nested loops. The outer loop runs m times and the inner loop runs n times. So we fill m * n cells, and each cell takes a fixed amount of work.

Here is the summary in one place.

🧩 What You’ve Learned

• ✅ A subsequence keeps order but allows gaps, while a substring must be a run of characters next to each other.
• ✅ The LCS is the longest subsequence shared by two strings, and we usually want its length first.
• ✅ The DP rule: if the current characters match, take the diagonal cell and add 1; if not, take the larger of the cell above and the cell to the left.
• ✅ The first row and first column are zeros, and the final answer sits in the bottom-right cell dp[m][n].
• ✅ Building the table costs O(m * n) time and O(m * n) space, far better than the brute-force 2^n blow-up.

🚀 What’s Next?

• 0/1 Knapsack Problem
• Dynamic Programming Patterns