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

ab
a
11 = 1
21 = 1 11 20
iehew iwhe => 3
ieh ihe

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m = text1.size(), n = text2.size();
        vector<int> prev(n + 1), cur(n + 1);
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (text1[i] == text2[j]) {
                    cur[j + 1] = prev[j] + 1;
                } else {
                    cur[j + 1] = max(prev[j + 1], cur[j]);
                }
            }
            swap(cur, prev);
        }
        return prev[n];
    }                                        
};

0,0 = 1
0,1 = 1
0,2 = 1
1,0 = 1
1,1 = 1
1,2 = 1
2,0 = 1
2,1 = 2 = 1,1 2,0 1,0 abc ac 1+1
2,2 = 2
3,0 = 1
3,1 = 2 abce ac max(3,0 2,1) + 1 (text[3] == text[1])
3,2 = 3 = 2,2 2 + 1
subsequence in both string
## Example dp[index1][index2]
Input: text1 = "abce", text2 = "ace"
Output: 3
Explanation: The longest common subsequence is "ace" and its length is 3.

biehewi iwhe => 3
1223

if the same
dp[i-1],[ j-1] + 1
else
max(dp[i][j-1], dp[i-1][j])
01
c ac 11
c cb 01 00
00 1
01 1 max(3,0 2,1) + 1 if(text[0] == text[1])
10
11
20
21

recursive
for index to end
if index text 1
recursive(text1.substr, index)

if substr of text1 have text2[index2]
dp[index2]{index1, length + 1} = max(dp[0 : index -1]) + 1
else
dp[index]