A catalog compared two SKU event streams. The new feed logged abcde. The warehouse logged ace. Shared letters in order: a, then c, then e — not a run, and not only a leading slice. The intern asked for the longest common substring and got 1. The Longest Common Prefix column walk returned "a". A few dozen codes returned. Log-sized SKUs were still enumerating subsequences when the job timed out.

Return the length of the longest common subsequence of text1 and text2. Order is kept. Holes are allowed. Contiguous is not required.

This is an interview writeup, not the reconstruction lecture. The LCS post owns the grid, the backward walk that emits one shared string, and the rolling-row length trick. Here we only fill match or skip so the last cell is the integer the prompt asked for.

The problem

Given two strings text1 and text2, return the length of their longest common subsequence. A subsequence is formed by deleting some (or no) characters without changing the order of the rest. If they share nothing, return 0.

text1 = "abcde", text2 = "ace"  →  3   ("ace")
text1 = "abc",   text2 = "abc"  →  3   (the string itself)
text1 = "abc",   text2 = "def"  →  0

Note: A subsequence may skip; a substring may not. "abcde" and "ace" share contiguous runs of length 1, and a subsequence of length 3. Longest Common Prefix is a leading slice of every string in a list — a column walk, not this two-string table.

Enumerating subsequences is the honest brute force

Every subsequence of text1 is a take-or-skip of each character. Test whether that sequence appears in text2 in order. Keep the longest that does. Correct. Exponential: O(2^m · n).

int lcsEnum(String text1, String text2) {
    int[] best = { 0 };
    from(text1, 0, new StringBuilder(), text2, best);
    return best[0];
}

void from(String a, int i, StringBuilder sub, String b, int[] best) {
    if (i == a.length()) {
        if (isSubseq(sub, b)) {
            best[0] = Math.max(best[0], sub.length());
        }
        return;
    }
    from(a, i + 1, sub, b, best);
    sub.append(a.charAt(i));
    from(a, i + 1, sub, b, best);
    sub.deleteCharAt(sub.length() - 1);
}

boolean isSubseq(CharSequence sub, String b) {
    int j = 0;
    for (int k = 0; k < b.length() && j < sub.length(); k++) {
        if (b.charAt(k) == sub.charAt(j)) {
            j++;
        }
    }
    return j == sub.length();
}

At m = 8 this is a rounding error. At log-sized strings you paid a subset tree for a question a prefix grid answers in O(mn): match both last letters, or skip one side?

Match or skip on prefixes

Let dp[i][j] be the LCS length of the first i characters of text1 and the first j of text2. Row 0 and column 0 stay 0 — empty prefixes share nothing. For i > 0, j > 0:

  • If text1.charAt(i - 1) == text2.charAt(j - 1), this pair extends the two shorter prefixes: dp[i][j] = dp[i - 1][j - 1] + 1.
  • Else you cannot take both. Skip the last of text1 or the last of text2: dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]).

Walk "abcde" against "ace":

text1 = a b c d e
text2 = a c e

        ''  a  c  e
   ''    0  0  0  0
   a     0  1  1  1
   b     0  1  1  1
   c     0  1  2  2
   d     0  1  2  2
   e     0  1  2  3

a vs a  match  diagonal 0 → 1
c vs c  match  diagonal 1 → 2
e vs e  match  diagonal 2 → 3
b and d are skips (up or left). length = dp[5][3] = 3

The Java is that fill. The prompt wants the length, so return dp[m][n] and stop:

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

Time is O(mn) — one cell per prefix pair. Space is O(mn) for the table. Identical strings fill the diagonal to n. Disjoint alphabets stay 0. Empty either side is 0.

Note: The table is 1-based prefixes; charAt is 0-based. Seeding row 0 with 0, 1, 2, … is an edit-distance cost table, a different job. Do not reconstruct the letters unless they switch the prompt.

What interviewers usually poke next

  • Emit one subsequence, not only the length. Keep the table and walk backward from (m, n). That reconstruction, including ties, lives on the LCS tutorial. Do not re-lecture it here.
  • Length only, less memory. Two rolling rows of size n + 1. You cannot reconstruct from two rows without extra bookkeeping; say so and point at the same tutorial.
  • They wanted a contiguous shared run. That is longest common substring. On a mismatch the substring recurrence resets; this one takes max(up, left).
  • They wanted a leading slice of many strings. That is Longest Common Prefix, a column walk, not an m × n grid.
  • Tokens, not characters. Same recurrence on word arrays; compare with equals, not charAt.

You are done with this problem when you can fill "abcde" / "ace" to 3 on a whiteboard, name why substring and LCP answer different questions, and say out loud why enumerating subsequences is correct and why the prefix grid is the same numbers in O(mn).