Algorithm Day95 - Longest Common Subsequence

Posted on In , , Views:

🧩 Problem Description

Given two strings text1 and text2, return the length of their longest common subsequence.
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.

If there is no common subsequence, return 0.

💬 Examples

Example 1

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

Example 2

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

Example 3

1
2
3
Input: text1 = "abc", text2 = "def"
Output: 0
Explanation: No common subsequence.

💡 Intuition

This is a classic dynamic programming problem.
Define dp[i][j] as the length of the longest common subsequence between text1[0..i) and text2[0..j).

Transitions:

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

We can implement this with a 2D DP table (size (m+1) × (n+1)) or optimize space to a 1D array by iterating rows and storing previous row values.

🔢 Java Code (2D DP)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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];
    }
}

🔢 Java Code (1D DP - space optimized)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length(), n = text2.length();
        int[] dp = new int[n + 1];
        for (int i = 1; i <= m; i++) {
            int prev = 0; // dp[i-1][j-1]
            for (int j = 1; j <= n; j++) {
                int temp = dp[j];
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    dp[j] = prev + 1;
                } else {
                    dp[j] = Math.max(dp[j], dp[j - 1]);
                }
                prev = temp;
            }
        }
        return dp[n];
    }
}

⏱ Complexity Analysis

  • Time: O(m × n), where m and n are the lengths of text1 and text2.
  • Space: O(m × n) for 2D DP, or O(n) for the optimized 1D DP.

✍️ Summary

  • Use DP with dp[i][j] representing LCS length for prefixes.
  • If characters match, extend dp[i-1][j-1]; otherwise take the max of neighboring states.
  • Space optimization to 1D is possible by careful ordering.

Related problems: lc-583 (Delete Operation for Two Strings), lc-718 (Maximum Length of Repeated Subarray).