Longest Common Subsequence

MediumDynamic ProgrammingString
Category: 2-D Dynamic Programming
Companies that ask this question:
AmazonGoogleFacebookMicrosoftBloomberg

Approach

Longest Common Subsequence

Problem Statement

Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

  • For example, "ace" is a subsequence of "abcde".

A common subsequence of two strings is a subsequence that is common to both strings.

Examples

Example 1:

Input: text1 = "abcde", text2 = "ace" 
Output: 3
Explanation: The longest common subsequence is "ace" with length 3.

Example 2:

Input: text1 = "abc", text2 = "abc"
Output: 3
Explanation: The longest common subsequence is "abc" with length 3.

Example 3:

Input: text1 = "abc", text2 = "def"
Output: 0
Explanation: There is no common subsequence.

Approach: Dynamic Programming

Intuition

The LCS problem has optimal substructure and overlapping subproblems, making it perfect for dynamic programming.

Key Insight:

  • If the last characters match: LCS includes this character
  • If they don't match: LCS is the longer of two options (exclude from text1 OR exclude from text2)

Algorithm

  1. Create a 2D DP table of size (m+1) × (n+1) where:

    • m = length of text1
    • n = length of text2
    • dp[i][j] = LCS length of text1[0..i-1] and text2[0..j-1]

  2. Initialize base cases:

    • dp[i][0] = 0 (empty text2)
    • dp[0][j] = 0 (empty text1)

  3. Fill the table using the recurrence:

    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])

  4. Return dp[m][n]

Why This Works

  • Characters match: We extend the LCS from the diagonal (both strings without last char)
  • Characters don't match: We take the best result from either:
    • Top cell: exclude current char from text1
    • Left cell: exclude current char from text2

Complexity Analysis

  • Time Complexity: O(m × n) - fill entire DP table
  • Space Complexity: O(m × n) - 2D DP table
    • Can be optimized to O(min(m,n)) using rolling arrays

Common Patterns

This problem demonstrates:

  1. 2D Dynamic Programming: State depends on two indices
  2. String DP: Character-by-character comparison
  3. Optimal Substructure: Optimal solution contains optimal solutions to subproblems
  4. Overlapping Subproblems: Same subproblems computed multiple times

Related Problems

  • Edit Distance (Levenshtein Distance)
  • Longest Increasing Subsequence
  • Shortest Common Supersequence
  • Minimum Insertions to Make String Palindrome

Tips

  1. Remember the recurrence: Match → diagonal + 1, No match → max(top, left)
  2. Index carefully: dp[i][j] uses text1[i-1] and text2[j-1]
  3. Space optimization: Can use 1D array by processing row-by-row
  4. Backtracking: To reconstruct actual LCS, trace back through DP table

Solution

java
1class Solution {
2    // Solution 1: 2D Dynamic Programming (Bottom-up)
3    public int longestCommonSubsequence(String text1, String text2) {
4        int m = text1.length();
5        int n = text2.length();
6        
7        // Create DP table
8        int[][] dp = new int[m + 1][n + 1];
9        
10        // Fill DP table
11        for (int i = 1; i <= m; i++) {
12            for (int j = 1; j <= n; j++) {
13                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
14                    // Characters match: take diagonal + 1
15                    dp[i][j] = dp[i - 1][j - 1] + 1;
16                } else {
17                    // No match: take max of top or left
18                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
19                }
20            }
21        }
22        
23        return dp[m][n];
24    }
25    
26    // Solution 2: Space-Optimized DP (1D array)
27    public int longestCommonSubsequenceOptimized(String text1, String text2) {
28        // Make text2 the shorter string
29        if (text1.length() < text2.length()) {
30            String temp = text1;
31            text1 = text2;
32            text2 = temp;
33        }
34        
35        int m = text1.length();
36        int n = text2.length();
37        
38        // Only need current and previous row
39        int[] prev = new int[n + 1];
40        int[] curr = new int[n + 1];
41        
42        for (int i = 1; i <= m; i++) {
43            for (int j = 1; j <= n; j++) {
44                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
45                    curr[j] = prev[j - 1] + 1;
46                } else {
47                    curr[j] = Math.max(prev[j], curr[j - 1]);
48                }
49            }
50            // Swap arrays
51            int[] temp = prev;
52            prev = curr;
53            curr = temp;
54        }
55        
56        return prev[n];
57    }
58    
59    // Solution 3: Recursive with Memoization (Top-down)
60    public int longestCommonSubsequenceMemo(String text1, String text2) {
61        int m = text1.length();
62        int n = text2.length();
63        Integer[][] memo = new Integer[m][n];
64        return dp(text1, text2, 0, 0, memo);
65    }
66    
67    private int dp(String text1, String text2, int i, int j, Integer[][] memo) {
68        // Base case: reached end of either string
69        if (i == text1.length() || j == text2.length()) {
70            return 0;
71        }
72        
73        // Check memo
74        if (memo[i][j] != null) {
75            return memo[i][j];
76        }
77        
78        // Match: extend LCS
79        if (text1.charAt(i) == text2.charAt(j)) {
80            memo[i][j] = 1 + dp(text1, text2, i + 1, j + 1, memo);
81        } else {
82            // No match: try both options
83            memo[i][j] = Math.max(
84                dp(text1, text2, i + 1, j, memo),
85                dp(text1, text2, i, j + 1, memo)
86            );
87        }
88        
89        return memo[i][j];
90    }
91    
92    // Bonus: Reconstruct the actual LCS string
93    public String getLCS(String text1, String text2) {
94        int m = text1.length();
95        int n = text2.length();
96        int[][] dp = new int[m + 1][n + 1];
97        
98        // Build DP table
99        for (int i = 1; i <= m; i++) {
100            for (int j = 1; j <= n; j++) {
101                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
102                    dp[i][j] = dp[i - 1][j - 1] + 1;
103                } else {
104                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
105                }
106            }
107        }
108        
109        // Backtrack to build LCS
110        StringBuilder lcs = new StringBuilder();
111        int i = m, j = n;
112        
113        while (i > 0 && j > 0) {
114            if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
115                lcs.append(text1.charAt(i - 1));
116                i--;
117                j--;
118            } else if (dp[i - 1][j] > dp[i][j - 1]) {
119                i--;
120            } else {
121                j--;
122            }
123        }
124        
125        return lcs.reverse().toString();
126    }
127}
128
Loading visualizer...