1143. Longest Common Subsequence

Description

Difficulty: Medium

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.

Example 1:

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

Example 2:

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

Example 3:

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

Constraints:

• 1 <= text1.length, text2.length <= 1000
• text1 and text2 consist of only lowercase English characters.

Solution

The fundamental idea at its heart is Dynamic Programming (DP), specifically a bottom-up tabulation approach. This powerful technique is used when you need to find an optimal solution (like the longest, shortest, or maximum) to a problem that can be broken down into smaller, self-similar subproblems.

1. Break It Down (Subproblems): Instead of directly trying to find the LCS of two long strings, we ask: "What's the LCS for all possible prefixes of these two strings?" For example, what's the LCS of text1's first 3 characters and text2's first 5 characters? We denote this subproblem's solution as dp[i][j], representing the LCS length for text1[0...i-1] and text2[0...j-1].

2. Build It Up (Tabulation): We start with the simplest subproblems: the LCS of an empty string with any other string (which is always 0). This forms the base of our dp table (dp[0][j] and dp[i][0] are all 0). Then, we systematically build up solutions for larger prefixes. To calculate dp[i][j], we look at the characters text1[i-1] and text2[j-1]:

   • If they match: Great! We've found another common character. This character extends the LCS of the strings without these current characters. So, we simply add 1 to the solution of the previous subproblem: dp[i-1][j-1] + 1.

   • If they don't match: We can't include both in the LCS. We have two choices: either exclude text1[i-1] and check dp[i-1][j], or exclude text2[j-1] and check dp[i][j-1]. Since we want the longest common subsequence, we take the maximum of these two options.

3. No Redundancy (Memoization/Tabulation): By filling the dp table in this systematic way, we ensure that whenever we need the solution to a subproblem (like dp[i-1][j-1] or dp[i-1][j]), it has already been computed and stored. This avoids re-calculating the same subproblem repeatedly, which is what makes dynamic programming efficient.

4. Final Answer: Once the entire dp table is filled, the cell dp[len1][len2] holds the solution for the original problem -- the LCS of the entire text1 and text2.

dp[i][j]	"" (j=0)	'a' (j=1)	'c' (j=2)	'e' (j=3)
"" (i=0)	0	0	0	0
'a' (i=1)	0	1	1	1
'b' (i=2)	0	1	1	1
'c' (i=3)	0	1	2	2
'd' (i=4)	0	1	2	2
'e' (i=5)	0	1	2	3

Essentially, this DP approach is like meticulously filling out a crossword puzzle. Each cell's answer depends on the answers to previously solved cells, and by solving them in the right order, you eventually arrive at the solution for the entire puzzle.

Code

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int len1 = text1.length();
        int len2 = text2.length();
        int[][] dp = new int[len1 + 1][len2 + 1];

        for (int i = 1; i <= len1; ++i) {
            for (int j = 1; j <= len2; ++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[len1][len2];
    }
}

Time Complexity: O(M * N)
Where M is text1.length() and N is text2.length(). The solution involves two nested loops, iterating through each cell of the M * N DP table. Each cell calculation is a constant-time operation.

Space Complexity: O(M * N)
A 2D dp array of size (M+1) * (N+1) is used to store all intermediate results.