Longest Common Subsequence (LC 1143)

Pattern: 2D Dynamic Programming
Difficulty: Medium
Key Concept: If last characters match, LCS is 1 + LCS of prefixes without both lasts; if not, take the better of dropping one side.

Problem Statement

Given two strings text1 and text2, return the length of their longest common subsequence. A subsequence is derived by deleting zero or more characters without changing the order of the remaining characters.

Input: two strings.
Output: non-negative int.

Examples:

• "abcde", "ace" → 3 ("ace").
• "abc", "abc" → 3.
• "abc", "def" → 0.

---

1. Algorithm & Pseudocode

Brute force

1. Enumerate all subsequences of text1 (2^m), check each against text2—impractical.
2. Better brute: recursion lcs(i,j) on prefixes text1[0..i), text2[0..j).
3. Without memo: exponential.

Pseudocode (recursive):

function lcs(i, j):
    if i == 0 or j == 0: return 0
    if text1[i-1] == text2[j-1]: return 1 + lcs(i-1, j-1)
    return max(lcs(i-1, j), lcs(i, j-1))

Optimal

1. Build dp[i][j] = LCS length for first i chars of text1 and first j of text2.
2. Transition:
   • If text1[i-1] == text2[j-1]: dp[i][j] = 1 + dp[i-1][j-1].
   • Else: dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
3. Answer dp[m][n]. Space-optimized: only need previous row.

---

2. Step-by-Step Analysis (Beginner-Friendly)

Why match case adds 1: Those two characters pair as the last matching pair in some optimal subsequence; remaining problem is strictly smaller prefixes.

Why mismatch takes max: You may discard the last char of text1 or of text2; you want whichever keeps more LCS.

Why 2D: Two sequences → state is a pair of positions (i,j).

---

3. The Dry Run

text1 = "ab", text2 = "acb". Rows i (0..2), cols j (0..3).

dp[i][j]	“”	a	c	b
“”	0	0	0	0
a	0	1	1	1
b	0	1	1	2

• (1,1): 'a'=='a' → 1+0=1.
• (2,3): 'b'=='b' → 1+dp[1][2]=1+1=2.

---

4. Java Solution

Brute Force

public class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        return lcs(text1, text2, text1.length(), text2.length());
    }

    private int lcs(String a, String b, int i, int j) {
        if (i == 0 || j == 0) {
            return 0;
        }
        if (a.charAt(i - 1) == b.charAt(j - 1)) {
            return 1 + lcs(a, b, i - 1, j - 1);
        }
        return Math.max(lcs(a, b, i - 1, j), lcs(a, b, i, j - 1));
    }
}

Time: O(2^(m+n)) worst. Space: O(m+n) stack.

Optimal

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

Time: O(m × n). Space: O(m × n).

Space O(min(m,n)) variant: single int[] row (rolling).

---

5. The “Java vs. Others” Edge

• charAt in loops avoids substring allocation.
• 2D int[][] is interview-clear; for huge strings discuss rolling array.
• LCS is classic setup for edit distance follow-ups (insert/delete/replace costs).

---

6. Complexity Summary

Approach	Time	Space	Notes
Naive recursion	Exponential	O(m+n)	Overlapping subproblems
2D DP	O(mn)	O(mn)	Easy to reconstruct LCS
1D DP	O(mn)	O(min(m,n))	Only length, harder to trace back