1143. Longest Common Subsequence

Longest Common Subsequence is the problem that makes 2D DP click — once you see the answer as a grid where each cell asks “do these two characters match?”, a whole shelf of string and edit-distance problems reads the same way. It’s a cornerstone of the 2D dynamic programming pattern, so the grid you build here is worth understanding cell by cell.

The problem

Given two strings, find the length of the longest sequence of characters that appears in both — in the same relative order, but not necessarily contiguous. Return 0 if they share nothing. (Full statement on LeetCode.)

For "abcde" and "ace", the longest common subsequence is "ace", so the answer is 3. Notice ace isn’t a substring of abcde — the b and d are skipped. That skipping is the whole reason a greedy scan doesn’t work.

Intuition: line the strings up on a grid

Think of the two strings on the axes of a grid. Cell dp[i][j] holds the LCS length of the first i characters of text1 and the first j characters of text2. Every cell answers one local question and leans on cells you’ve already filled.

Compare the last characters of the two prefixes, text1[i-1] and text2[j-1]:

• They match. Then this shared character extends whatever was best without it. Take the diagonal cell and add one: $dp[i][j] = dp[i-1][j-1] + 1$.
• They don’t match. At least one of these two characters can’t be in the answer, so drop one string by a character and keep the better result: $dp[i][j] = \max(dp[i-1][j],\ dp[i][j-1])$.

$$dp[i][j] = \begin{cases} dp[i-1][j-1] + 1 & \text{if } text1[i-1] = text2[j-1] \\ \max(dp[i-1][j],\ dp[i][j-1]) & \text{otherwise} \end{cases}$$

The base row and column are all zeros: an empty prefix shares nothing with anything. That’s why the table has an extra row and column — the zero border removes every edge case, so no cell ever reaches out of bounds.

Solution

Build the table left to right, top to bottom. Using m+1 × n+1 lets the zero border do the boundary work for free:

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length(), n = text2.length();
        // dp[i][j] = LCS length of text1's first i chars and text2's first j chars.
        // Row 0 and column 0 stay zero: an empty prefix matches nothing.
        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)) {
                    // Characters match: extend the diagonal by one.
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    // No match: carry forward the best of dropping either char.
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[m][n];
    }
}

Each row only reads the row above it and the cell to its left, so the full table is more memory than you need. Keep two rows — previous and current — and swap them each pass. Looping so the shorter string is on the inner axis keeps that row as small as possible:

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        // Make text2 the shorter string so the rolling row is min(m, n).
        if (text1.length() < text2.length()) {
            String t = text1; text1 = text2; text2 = t;
        }
        int m = text1.length(), n = text2.length();
        int[] prev = new int[n + 1];
        int[] cur = new int[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)) {
                    cur[j] = prev[j - 1] + 1;         // diagonal + 1
                } else {
                    cur[j] = Math.max(prev[j], cur[j - 1]);  // above vs. left
                }
            }
            int[] tmp = prev; prev = cur; cur = tmp;  // roll: cur becomes prev
        }
        return prev[n];
    }
}

Complexity

Approach	Time	Space
Full 2D table	$O(m \cdot n)$	$O(m \cdot n)$
Rolling two rows	$O(m \cdot n)$	$O(\min(m, n))$

Both fill every one of the $m \cdot n$ cells once. The rolling version keeps only two rows in flight, so its footprint tracks the shorter string.

In an interview

Draw the little grid before you touch code — put one string across the top, one down the side, and fill a couple of cells out loud. That makes the two branches obvious: a diagonal step on a match, a max of up-and-left on a mismatch. The trap is confusing subsequence with substring. A substring must be contiguous, which resets the count to zero on a mismatch and needs a separate running maximum; subsequence lets you skip characters, which is exactly why the mismatch branch carries the best result forward instead of dropping to zero. Naming that distinction early tells the interviewer you picked the recurrence on purpose.

If they push on memory, offer the rolling two-row version and mention swapping so the shorter string sits on the inner axis. The same fill-the-grid, look-at-your-neighbors idea drives Unique Paths, where each cell sums the one above and the one to its left instead of comparing characters — the 2D DP pattern hub walks through where this grid shape keeps reappearing.

References

• LeetCode 1143 — Longest Common Subsequence