# 1143. Longest Common Subsequence (Medium)

https://leetcode.com/problems/longest-common-subsequence/

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.

## Solutions

### 1.

``````class Solution {

// This problem reminds me another problem longest consecutive common subsequence. The idea is similar that both
// employ dynamic programming. Here, I will implement the solution for longest consecutive common subsequence.

private int longestConsecutiveCommonSubsequence(String text1, String text2) {
int ans = 0;

if (text1 == null || text1.length() == 0 || text2 == null || text2.length() == 0) {
return ans;
}

int len1 = text1.length();
int len2 = text2.length();

// subject to text1.length() < text2.length()

// row represents the length of text2, col represents the length of text1
// initially, values for every cell is 0 by default.
int[][] dp = new int[len2 + 1][len1 + 1];

for (int i = 1; i <= len2; i++) {
for (int j = 1; j <= len1; j++) {
if (text1.charAt(j - 1) == text2.charAt(i - 1)) {
// text1 and text2 both move forward one step
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = 0;
}

ans = Math.max(ans, dp[i][j]);
}
}

return ans;
}

public int longestCommonSubsequence(String text1, String text2) {
if (text1 == null || text1.length() == 0 || text2 == null || text2.length() == 0) {
return 0;
}

int len1 = text1.length();
int len2 = text2.length();

// row represents the length of text1, col represents the length of text2
// initially, values for every cell is 0 by default.
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)) {
// text1 and text2 both move forward one step
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]);
}
}
}

return dp[len1][len2];
}

private int max(int x, int y, int z) {
int tmp = Math.max(x, y);

return Math.max(tmp, z);
}
}
``````

### 2.

``````class Solution2 {

// Inspired by https://leetcode.com/problems/longest-common-subsequence/discuss/349150/Simple-DP-in-Python-O(mn)-time-O(n)-memory-explained

// This solution saved more memory space. But a little different from the original one because we did not strictly
// make the text1 and text2 subject to text1.length > text2.length.

public int longestCommonSubsequence(String text1, String text2) {
if (text1 == null || text1.length() == 0 || text2 == null || text2.length() == 0) {
return 0;
}

int len1 = text1.length();
int len2 = text2.length();

// dp[curP][j] only consider the results of dp[curP-1][j], dp[curP-1][j-1] and dp[curP][j-1].
// results of dp[curP-2][*] will never be used later.
// So we can simplify the curP as current, curP-1 as previous, thus we only have to allocate
// int[len1+1] space and that will be enough.

int[][] dp = new int[len2 + 1];

for (int i = 1; i <= len1; i++) {

// parity
int prevP = (i - 1) % 2;
int curP = i % 2;

dp[curP] = 0;

for (int j = 1; j <= len2; j++) {
if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
// text1 and text2 both move forward one step
dp[curP][j] = dp[prevP][j - 1] + 1;
} else {
dp[curP][j] = max(dp[prevP][j - 1], dp[prevP][j], dp[curP][j - 1]);
}
}
}

return dp[len1 % 2][len2];
}

private int max(int x, int y, int z) {
int tmp = Math.max(x, y);

return Math.max(tmp, z);
}
}
``````