<p>Given two strings <code>text1</code> and <code>text2</code>, return <em>the length of their longest <strong>common subsequence</strong>. </em>If there is no <strong>common subsequence</strong>, return <code>0</code>.</p>

<p>A <strong>subsequence</strong> 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.</p>

<ul>
	<li>For example, <code>&quot;ace&quot;</code> is a subsequence of <code>&quot;abcde&quot;</code>.</li>
</ul>

<p>A <strong>common subsequence</strong> of two strings is a subsequence that is common to both strings.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> text1 = &quot;abcde&quot;, text2 = &quot;ace&quot; 
<strong>Output:</strong> 3  
<strong>Explanation:</strong> The longest common subsequence is &quot;ace&quot; and its length is 3.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> text1 = &quot;abc&quot;, text2 = &quot;abc&quot;
<strong>Output:</strong> 3
<strong>Explanation:</strong> The longest common subsequence is &quot;abc&quot; and its length is 3.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> text1 = &quot;abc&quot;, text2 = &quot;def&quot;
<strong>Output:</strong> 0
<strong>Explanation:</strong> There is no such common subsequence, so the result is 0.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= text1.length, text2.length &lt;= 1000</code></li>
	<li><code>text1</code> and <code>text2</code> consist of only lowercase English characters.</li>
</ul>

class Solution {
public:
    // int solve(string& text1, string& text2, int m, int n, int i, int j,vector<vector<int>>&dp){
    //     if(i==m)return 0;
    //     if(j==n)return 0;
    //     if(dp[i][j]!=-1)return dp[i][j];
    //     int ans=0;
    //     if(text1[i]==text2[j]){
    //         ans = 1 + solve(text1,text2,m,n,i+1,j+1,dp);
    //     }
    //     else{
    //         ans = max(solve(text1,text2,m,n,i+1,j,dp),solve(text1,text2,m,n,i,j+1,dp));
    //     }
    //     dp[i][j]=ans;
    //     return dp[i][j];
    // }
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        if(n<=1)return n;
        vector<int>temp;
        temp.push_back(nums[0]);
        for(int i=1;i<n;i++){
            if(nums[i]>temp.back())temp.push_back(nums[i]);
            else{
                int index = lower_bound(temp.begin(),temp.end(),nums[i])-temp.begin();
                temp[index]=nums[i];
            }
        }
        return temp.size();
    }
    int longestCommonSubsequence(string text1, string text2) {
        int m = text1.length();
        int n = text2.length();
        // vector<vector<int>>dp(m,vector<int>(n,-1));
        // return solve(text1,text2,m,n,0,0,dp);
        vector<int>nums;
        unordered_map<char,vector<int>>mp;
        for(int i=n-1;i>=0;i--){
            mp[text2[i]].push_back(i);
        }
        for(int i=0;i<m;i++){
            if(mp.find(text1[i])!=mp.end()){
                for(auto j : mp[text1[i]])nums.push_back(j);
            }
        }
        return lengthOfLIS(nums);
    }
};
17668