Longest Common Subsequence

Medium20–25 min

Topics

Dynamic ProgrammingString

Companies

AmazonGoogleAdobe

Given two strings, find the length of their longest common subsequence — the longest sequence of characters that appears in both strings in the same relative order, though not necessarily touching. If the two strings share nothing in common this way, the answer is 0. Comparing the two strings one trailing character at a time exposes a clean split: when the last characters of both remaining prefixes agree, that character has to belong to some longest common subsequence, so it's taken and both prefixes shrink together. When they disagree, the best answer either ignores the last character of the first string or the last character of the second — trying both and keeping the larger result is always correct, since one of those two prefixes must still contain an optimal answer. Filling a table of these prefix-pair answers from the smallest prefixes upward turns an exponential search into a single pass over every (i, j) pair exactly once.

Test Case 1:

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

Output:3

Explanation:Picking a, c, e out of "abcde" in order matches "ace" exactly — no way to line up 4 letters in the same relative order from both strings.

Test Case 2:

Input:text1 = "abc", text2 = "def"

Output:0

Explanation:Not a single letter is shared between the two strings, so the only common subsequence is the empty one.

Test Case 3:

Input:text1 = "", text2 = "abc"

Output:0

Explanation:An empty string has no subsequence at all except the empty one, so the longest common subsequence has length 0.

Constraints

◆0 ≤ text1.length, text2.length ≤ 12
◆text1 and text2 consist only of lowercase English letters

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Recursive Without Memoization

Brute

At every pair of positions (i, j) there are only two live moves. When the current tail characters agree, that character must be part of an optimal common subsequence, so lock it in and shrink both strings by one. When they disagree, at least one of the two tail characters can be dropped without losing the best answer — but which one is unknown up front, so both possibilities are tried and the larger result kept. The catch is that the same (i, j) pair gets reached through many different sequences of drops, and each time it is solved completely from scratch again.

TimeO(2ⁿ⁺ᵐ)

SpaceO(n+m)

Java

Try it out

class Solution {
    private String text1, text2;

    public int longestCommonSubsequence(String text1, String text2) {
        this.text1 = text1;
        this.text2 = text2;
        return solve(text1.length(), text2.length());
    }

    private int solve(int i, int j) {
        if (i == 0 || j == 0) return 0;
        if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
            return 1 + solve(i - 1, j - 1);
        }
        return Math.max(solve(i - 1, j), solve(i, j - 1));
    }
}

Optimal — Bottom-Up 2D DP

Optimal

Build a table dp[i][j] holding the answer for the first i characters of text1 against the first j characters of text2, filling it in order from the smallest prefixes up. Every cell needs only the three cells directly above, to the left, and diagonally above-left of it, so each one is computed exactly once instead of being re-derived on demand through recursion. The very last cell, using the full length of both strings, is the final answer.

TimeO(n·m)

SpaceO(n·m)