// 1143. Longest Common Subsequence

//

// 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.

//

//

// Runtime 24 ms Beats 36.58% of users with Java

// Memory 50.50 MB Beats 10.75% of users with Java

class Solution {

public int longestCommonSubsequence(String text1, String text2) {

int len1 = text1.length();

int len2 = text2.length();

int[][] matrix = 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)) {

matrix[i][j] = matrix[i - 1][j - 1] + 1;

}

matrix[i][j] = Math.max(matrix[i][j], Math.max(matrix[i - 1][j], matrix[i][j - 1]));

}

}

return matrix[len1][len2];

}

}

// Runtime 19 ms Beats 90.79% of users with Java

// Memory 50.85 MB Beats 9.13% of users with Java

class Solution {

public int longestCommonSubsequence(String text1, String text2) {

int len1 = text1.length();

int len2 = text2.length();

int[][] matrix = 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)) {

matrix[i][j] = matrix[i - 1][j - 1] + 1;

} else {

matrix[i][j] = Math.max(matrix[i - 1][j], matrix[i][j - 1]);

}

}

}

return matrix[len1][len2];

}

}