Longest Common Subsequence

Longest Common Subsequence is the parent of many string problems. The interviewer uses it to see if you can compare two strings with a 2D grid. Once you understand this one grid, edit distance and many others become easy.

🎯 The Problem

You get two strings and you return the length of their longest common subsequence.

• You compare two strings.
• A subsequence keeps the original order but the characters need not sit next to each other.
• You want the longest run of characters that appears in both strings, in the same order.
• You return a length, not the actual characters.

For "abcde" and "ace", the letters a, c, and e all show up in "abcde" in that same order. So the longest common subsequence is "ace", and its length is 3.

Input:  text1 = "abcde", text2 = "ace"
Output: 3

Explanation: The longest common subsequence is "ace", which has length 3.

Here is the matching idea. We line up both strings and pick out the shared letters in order.

🐢 Approach 1: Plain Recursion (Brute Force)

Compare the two strings from the front and branch on every mismatch.

The idea:

• Look at the first character of each string.
• If they match, keep it and move both strings forward by one.
• If they differ, try two things and take the bigger result.

How it works:

• Skip the first character of string one, or skip the first of string two.
• When either string runs out, nothing is left to match, so the length is zero.

Why it is weak:

• A mismatch branches into two calls.
• The same pair of positions gets solved again and again.
• Time grows about O(2^(m+n)). Too slow.

Here is the plain recursion code:

def longest_common_subsequence(text1, text2):
    def dfs(i, j):
        if i == len(text1) or j == len(text2):
            return 0
        if text1[i] == text2[j]:
            return 1 + dfs(i + 1, j + 1)
        return max(dfs(i + 1, j), dfs(i, j + 1))

    return dfs(0, 0)

⚡ Approach 2: Memoization (Better)

Store each position pair so it is solved only once.

The idea:

• The answer for “string one from index i, string two from index j” never changes.
• So save it the first time you compute it.

How it works:

• Keep a 2D table keyed by the two indexes.
• The first time you solve a pair, write it down.
• Next time the pair comes up, read the saved value.

Why it is fast:

• Each position pair runs once.
• Time drops to O(m × n), where m and n are the string lengths.

Here is the memoized recursion:

from functools import lru_cache


def longest_common_subsequence(text1, text2):
    @lru_cache(None)
    def dfs(i, j):
        if i == len(text1) or j == len(text2):
            return 0
        if text1[i] == text2[j]:
            return 1 + dfs(i + 1, j + 1)
        return max(dfs(i + 1, j), dfs(i, j + 1))

    return dfs(0, 0)

⚡ Approach 3: Bottom-Up Tabulation (Better)

Build a grid from the smallest cases up, with no recursion.

The idea:

• Make a 2D table dp with an extra row and column of zeros.
• The cell dp[i][j] holds the LCS length of the first i and first j characters.

How it works:

• On a match, the cell is one plus the diagonal cell up and to the left.
• On a mismatch, the cell is the larger of the cell above and the cell to the left.
• Fill the grid in order so every cell already has its three neighbors ready.

Why it is fast:

• Each cell is filled once.
• Time is O(m × n). The bottom-right cell is the answer.

Here is the bottom-up table code:

def longest_common_subsequence(text1, text2):
    dp = [[0] * (len(text2) + 1) for _ in range(len(text1) + 1)]

    for i in range(len(text1) - 1, -1, -1):
        for j in range(len(text2) - 1, -1, -1):
            if text1[i] == text2[j]:
                dp[i][j] = 1 + dp[i + 1][j + 1]
            else:
                dp[i][j] = max(dp[i + 1][j], dp[i][j + 1])

    return dp[0][0]

⚡ Approach 4: Space-Optimized Two Rows (Best)

Keep only the two rows the grid rule actually needs.

The idea:

• Each cell reads only the row above and the current row.
• So the whole grid is never needed at once.

How it works:

• Keep a previous row and a current row.
• Fill the current row using the previous row.
• When the row is done, the current row becomes the previous row.

Why it is best:

• Time stays O(m × n), just as fast.
• Memory drops from a full grid to two rows, so it is O(n).

Here is the 2D grid filling for "abcde" and "ace". Rows are the first string, columns are the second. Each cell is an LCS length.

Steps to Solve

1. Let m and n be the lengths of the two strings.
2. Make a 2D table dp of size (m + 1) by (n + 1), filled with zeros. The extra row and column stand for empty strings.
3. Loop i from 1 to m and j from 1 to n.
4. If the characters at i - 1 and j - 1 match, set dp[i][j] to dp[i - 1][j - 1] + 1.
5. If they do not match, set dp[i][j] to the larger of dp[i - 1][j] and dp[i][j - 1].
6. After the loops, dp[m][n] holds the length of the longest common subsequence.

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

int max(int a, int b) { return a > b ? a : b; }

int lcs(const char *a, const char *b) {
    int m = strlen(a), n = strlen(b);
    int dp[101][101] = {0};               // extra row/col of zeros

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (a[i - 1] == b[j - 1])
                dp[i][j] = dp[i - 1][j - 1] + 1;   // match: diagonal + 1
            else
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); // carry best
        }
    }
    return dp[m][n];
}

int main(void) {
    printf("%d\n", lcs("abcde", "ace"));
    return 0;
}

3

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

int lcs(const string& a, const string& b) {
    int m = a.size(), n = b.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0)); // zero border

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (a[i - 1] == b[j - 1])
                dp[i][j] = dp[i - 1][j - 1] + 1;          // match
            else
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); // carry best
        }
    }
    return dp[m][n];
}

int main() {
    cout << lcs("abcde", "ace") << endl;
    return 0;
}

3

public class Lcs {
    public static int lcs(String a, String b) {
        int m = a.length(), n = b.length();
        int[][] dp = new int[m + 1][n + 1];          // zero border

        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] = dp[i - 1][j - 1] + 1;  // match
                else
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return dp[m][n];
    }

    public static void main(String[] args) {
        System.out.println(lcs("abcde", "ace"));
    }
}

3

def lcs(a, b):
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]   # zero border

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1          # match: diagonal + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])  # carry best
    return dp[m][n]


print(lcs("abcde", "ace"))

3

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] = dp[i - 1][j - 1] + 1;            // match
      } else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); // carry best
      }
    }
  }
  return dp[m][n];
}

console.log(lcs("abcde", "ace"));

3

Let us walk through the Python version line by line. The why behind each line explains the whole grid.

m, n = len(a), len(b) gets both string lengths. The grid will be sized from these.

dp = [[0] * (n + 1) for _ in range(m + 1)] builds the grid with an extra row and column of zeros. That border stands for an empty string. The LCS with an empty string is always zero, which seeds the whole table.

for i in range(1, m + 1): and for j in range(1, n + 1): walk every pair of prefixes. We start at one, not zero, because row zero and column zero are the empty-string border.

if a[i - 1] == b[j - 1]: checks the current characters. The i - 1 and j - 1 line up the grid index with the real string index, because the grid is shifted by one for the border.

dp[i][j] = dp[i - 1][j - 1] + 1 is the match rule. When the characters match, we extend the answer from the diagonal cell. That diagonal cell is the best length before either of these characters, so adding one is correct.

dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) is the mismatch rule. When the characters differ, we drop one character from one string and take the better of the two choices. The cell above means dropping a character from one string, and the cell to the left means dropping from the other.

return dp[m][n] reads the final answer. The bottom-right cell uses both whole strings, so it holds the full LCS length.

⏱️ Time and Space Complexity

Plain recursion is exponential, since it re-solves the same position pairs. Memoization and 2D tabulation both visit each of the m times n cells once, so they run in O(m times n) time. The space-optimized version keeps only two rows, so it uses O(n) memory while staying just as fast.

🧩 Key Takeaways

• ✅ A subsequence keeps order but does not need characters next to each other.
• ✅ The grid cell dp[i][j] holds the LCS of the first i and first j characters.
• ✅ On a match, take the diagonal cell plus one.
• ✅ On a mismatch, take the larger of the cell above and the cell to the left.
• ✅ Two rolling rows are enough, which cuts memory from a full grid to one line.

🚀 What’s Next?

• Unique Paths
• Coin Change 2