[link](https://leetcode.com/problems/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.

#### Example3:

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.

---

The code initializes a 2D list dp with dimensions (len(text1) + 1) x (len(text2) + 1). Each element dp[i][j] represents the length of the longest common subsequence between the substrings text1[i:] and text2[j:].

The outer loop iterates through the characters of text1 in reverse order, starting from the second-to-last character and going back to the first character. The inner loop iterates through the characters of text2 in reverse order, following the same pattern as the outer loop.

For each pair of characters (text1[i], text2[j]), the code compares them. If they are equal, it means that they contribute to the common subsequence, so the length of the longest common subsequence is increased by 1 from the next positions (i + 1, j + 1).

If the characters are not equal, the code takes the maximum length of the subsequences formed by excluding one character from either text1 or text2. This is done by comparing dp[i + 1][j] and dp[i][j + 1], representing the lengths of the subsequences formed by excluding the current character from text1 and text2, respectively. After completing the nested loops, the length of the longest common subsequence between text1 and text2 is stored in dp[0][0].

#### Solution 1

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        dp = [[0 for j in range(len(text2) + 1)] for i in range(len(text1) + 1)]

        for i in range(len(text1) - 1, -1, -1):
            for j in range(len(text2) - 1, -1, -1):
                if text1[i] == text2[j]:
                    dp[i][j] = 1 + dp[i + 1][j + 1]
                else:
                    dp[i][j] = max(dp[i + 1][j], dp[i][j + 1])
                

        return dp[0][0]

O(T): O(n * m)
O(S): O(n * m)