<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 longestCommonSubsequence(string text1, string text2) {
        int m = text1.size();
        int n = text2.size();

        // Brute-force n^2 approach -> getting TLE
        // vector<vector<int>> dp(m+1, vector<int>(n+1, 0));

        // for(int i=1; i<=m; i++){
        //     for(int j=1;j<=n; j++){
        //         if(text1[i-1] == text2[j-1]){
        //             dp[i][j] = dp[i-1][j-1] + 1;
        //         }
        //         else{
        //             dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
        //         }
        //     }
        // }

        // for(int i=0; i<=m; i++){
        //     for(int j=0; j<=n; j++){
        //         cout << dp[i][j] << " ";
        //     }

        //     cout << endl;
        // }

        // return dp[m][n];


        // **Optimized**  nlogn //

        /*
        Approach: Transform to Longest Increasing Subsequence (LIS)
        The idea is to reduce the problem of finding the Longest Common Subsequence (LCS) to the problem of finding the Longest         Optimally when the sequences are subsequences of the same or similar sequences.

        Transform the Problem:

        Convert text1 into indices relative to text2.
        Then, find the LIS on these indices.
        Explanation:

        This approach works in 
        \U0001d442(\U0001d45blog\U0001d45b)
        O(nlogn) time using binary search when applied on the transformed indices.
        Steps:
        Map Characters: Map each character in text2 to its positions in text1.
        Transform: For each character in text1, collect the positions of matching characters in text2.
        Apply LIS: Find the Longest Increasing Subsequence on these positions.
        */
        
        unordered_map<char, vector<int>> pos_map;

        for(int i=0; i<text2.size(); i++){
            pos_map[text2[i]].push_back(i);
        }

        vector<int> sequence;

        for(char c: text1){
            if(pos_map.find(c) != pos_map.end()){
                for(auto it = pos_map[c].rbegin(); it != pos_map[c].rend(); it++){
                    sequence.push_back(*it);
                }
            }
        }


        return lengthLIS(sequence);



    }

private:
    int lengthLIS(const vector<int>& nums){
        vector<int> lis;

        for(auto& num : nums){
            int curr = num;

            auto it = lower_bound(lis.begin(), lis.end(), curr);

            if(it == lis.end()){
                lis.push_back(curr);
            }
            else{
                *it = curr;
            }
        }

        return lis.size();
    }
};
18369