Amazon

Microsoft

Tencent

2020-05-25

## 1143. Longest Common Subsequence

### Question:

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. (eg, “ace” is a subsequence of “abcde” while “aec” is not). A common subsequence of two strings is a subsequence that is common to both strings.

If there is no common subsequence, return 0.

#### 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 <= 1000`
• `1 <= text2.length <= 1000`
• The input strings consist of lowercase English characters only.

### Solution:

Similar to LeetCode Question 1035 and LeetCode Question 1458, we are using DP to record the maximum of common subsequence of current position of i, j. So if the character in i, j are not matched, dp function is `dp[i][j] = Max(dp[i-1][j], dp[i][j-1])`. Otherwise, it will be `dp[i][j] = dp[i-1][j-1] + 1`.

Time: O(nm) Space: O(nm)

``````class Solution {
public int longestCommonSubsequence(String text1, String text2) {
int n = text1.length();
int m = text2.length();
int[][] dp = new int[n + 1][m + 1];
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; 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[n][m];
}
}
``````

It could also be solved with Time: O(n*m) Space: Min(O(n), O(m)) by using a rolling dp array.

``````class Solution {
public int longestCommonSubsequence(String text1, String text2) {
int n = text1.length();
int m = text2.length();
// To save memory by creating the array with smallest length
if (m > n) return longestCommonSubsequence(text2, text1);
int[][] dp = new int[m+1];
for (int i = 0; i < n; i++) {
int index = (i + 1) % 2;
for (int j = 0; j < m; j++) {
if (text1.charAt(i) == text2.charAt(j)) {
dp[index][j + 1] = dp[i % 2][j] + 1;
} else {
dp[index][j + 1] = Math.max(dp[index][j], dp[i % 2][j + 1]);
}
}
}
return dp[n % 2][m];
}
}
``````

Follow Up question for this Problem:

1. Find/Print any Longest Common Subsequence
2. Find/Print all Longest Common Subsequence

Both question will need to borrow the dp array from solution 1.
1. Find/Print any Longest Common Subsequence

``````public String getAnyLCS(String text1, String text2, int[][] dp) {
StringBuilder sb = new StringBuilder();
int i = text1.length(), j = text2.length();
while (i > 0 && j > 0) {
if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
sb.append(text1.charAt(i - 1));
i--;
j--;
} else if (dp[i - 1][j] >= dp[i][j - 1]) {
i--;
} else {
j--;
}
}
return sb.reverse().toString();
}
``````

2. Find/Print all Longest Common Subsequence

``````public Set<String> getAllLCS(String text1, String text2, int[][] dp) {
Set<String> results = new HashSet<>();
dfs("", text1.length(), text2.length(), text1, text2, dp, results);
return results;
}

private void dfs(String s, int i, int j, String text1, String text2, int[][] dp, Set<String> results) {
if (i == 0 || j == 0) {
return;
}

if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
dfs(s + text1.charAt(i - 1), i - 1, j - 1, text1, text2, dp, results);
} else {
if (dp[i - 1][j] >= dp[i][j - 1]) {
dfs(s, i - 1, j, text1, text2, dp, results);
}

if (dp[i][j - 1] >= dp[i - 1][j]) {
dfs(s, i, j - 1, text1, text2, dp, results);
}
}
}
``````