Problem
You are given two stringstext1 and text2. Return the length of their longest common subsequence.
A subsequence is created by deleting zero or more characters without changing the order of the remaining characters. The characters in a subsequence do not need to be consecutive.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
text1 = "abcde"
text2 = "ace"Output
3"ace"Solution(s)
Memoization Approach
To find the longest common subsequence, we start from an index in both strings.If the characters at the current indices are equal, that character can be included in the common subsequence. We then move forward in both strings.
If the characters are different, we have two choices. We can skip the current character from
text1 or skip the current character from text2. We take the maximum result from both choices.
If we reach the end of either string, no more common characters can be found.
The same pair of indices can be reached multiple times, so we store the result for each pair using memoization.
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
Integer[][] memo = new Integer[text1.length()][text2.length()];
return longestCommonSubsequenceHelper(text1, text2, 0, 0, memo);
}
private int longestCommonSubsequenceHelper(String text1, String text2, int i, int j, Integer[][] memo) {
// Reached the end of either string
if (i >= text1.length() || j >= text2.length())
return 0;
// Return the cached result
if (memo[i][j] != null)
return memo[i][j];
// Characters match, include the current character
if (text1.charAt(i) == text2.charAt(j))
return memo[i][j] = 1 + longestCommonSubsequenceHelper(text1, text2, i + 1, j + 1, memo);
// Characters do not match, skip one character from either string
return memo[i][j] = Math.max(
longestCommonSubsequenceHelper(text1, text2, i + 1, j, memo),
longestCommonSubsequenceHelper(text1, text2, i, j + 1, memo)
);
}
}
Complexity
There are at mostm × n different combinations of indices, and each combination is calculated only once, resulting in O(m × n) time complexity. The memoization table requires O(m × n) space.
Tabulation Approach
We can also solve the problem using bottom-up Dynamic Programming.Let
dp[i][j] represent the length of the longest common subsequence between the first i characters of text1 and the first j characters of text2.
If either string is empty, there is no common subsequence, so the corresponding value is
0.
If the current characters match, we include that character and add
1 to the result from the previous characters.
If the characters are different, we skip one character from either string and take the larger result.
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++) {
// Characters match.
if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
dp[i][j] = 1 + dp[i - 1][j - 1];
} else {
// Skip one character from either string.
dp[i][j] = Math.max(
dp[i - 1][j],
dp[i][j - 1]
);
}
}
}
return dp[m][n];
}
}
Complexity
The DP table containsm × n states, and each state is calculated once, resulting in O(m × n) time complexity. The DP table requires O(m × n) space.
Space Optimized Approach
In the tabulation approach, each row only depends on the values from the previous row and the current row.Therefore, instead of storing the entire
m × n DP table, we can store only one row. The current values are updated from left to right while keeping track of the previous diagonal value.
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
int m = text1.length();
int n = text2.length();
int[] dp = new int[n + 1];
for (int i = 1; i <= m; i++) {
int previous = 0;
for (int j = 1; j <= n; j++) {
int temp = dp[j];
// Characters match.
if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
dp[j] = 1 + previous;
} else {
dp[j] = Math.max(dp[j], dp[j - 1]);
}
previous = temp;
}
}
return dp[n];
}
}
Complexity
Each combination of characters is processed once, resulting inO(m × n) time complexity. The one-dimensional DP array requires O(n) space.
