Longest Common Subsequence

Problem in plain words

Given two strings, find the length of the longest sequence of characters that appears in both, in the same order, though not necessarily side by side. Return 0 if they share nothing.

For example, "stone" and "longest" share the subsequence "one", so the answer is 3.

Intuition

Compare the last characters of two prefixes. If they are equal, that character can end a common subsequence, so the answer is one more than the answer for both prefixes without it. If they differ, at least one of them is not part of the best match, so drop one character from one string or the other and keep the better result. These overlapping subproblems over prefix pairs are the heart of the LCS lesson.

Approach

1. State: dp[i][j] is the LCS length of the first i characters of text1 and the first j characters of text2.
2. Recurrence: if text1[i - 1] == text2[j - 1], then dp[i][j] = dp[i - 1][j - 1] + 1; otherwise dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]).
3. Base cases: row 0 and column 0 are 0, because an empty prefix shares nothing.
4. Order: fill rows i = 1..m, and within each row columns j = 1..n. The answer is dp[m][n].

Dry run

Input: text1 = "abc", text2 = "bac". Rows are prefixes of text1, columns are prefixes of text2.

The answer is 2, for example "ac" or "bc".

Java solution

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length(), 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];
    }
}

Python solution

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m, n = len(text1), len(text2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if text1[i - 1] == text2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        return dp[m][n]

Complexity

Edge cases and common mistakes

• No shared characters: the table stays all zeros and the answer is 0.
• Confusing subsequence with substring: a substring must be contiguous. For substrings the mismatch case resets to 0 instead of taking a max.
• Off-by-one indexing: with a table of size (m + 1) x (n + 1), row i refers to character text1[i - 1].
• Greedy matching: matching the first equal characters you see can lock you into a worse alignment; only the DP considers every option.