<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 binarySearchReplace(vector<int>& seq, int pos) {
    int low = 0, high = seq.size();
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (seq[mid] < pos)
            low = mid + 1;
        else
            high = mid;
    }
    return low;
}

// Function to find the length of the longest common subsequence using Hunt-Szymanski Algorithm
int huntSzymanskiLCS(const string& A, const string& B) {
    int n = A.size();
    int m = B.size();

    // Step 1: Build a map where each character in B is associated with its positions
    map<char, vector<int>> positionMap;
    for (int j = 0; j < m; ++j) {
        positionMap[B[j]].push_back(j);
    }

    // Step 2: Create a sequence to maintain the current LCS length
    vector<int> sequence;

    // Step 3: Traverse the characters of string A
    for (int i = 0; i < n; ++i) {
        char ch = A[i];
        
        // If the character exists in B, process its positions
        if (positionMap.find(ch) != positionMap.end()) {
            const vector<int>& positions = positionMap[ch];

            // Step 4: Traverse the positions in reverse order
            for (int k = positions.size() - 1; k >= 0; --k) {
                int pos = positions[k];

                // Perform binary search and replace the position in the sequence
                int idx = binarySearchReplace(sequence, pos);
                if (idx == sequence.size()) {
                    sequence.push_back(pos);  // Extend the LCS
                } else {
                    sequence[idx] = pos;  // Update the sequence
                }
            }
        }
    }

    // The length of the sequence is the length of the LCS
    return sequence.size();
}

    int longestCommonSubsequence(string A, string B) {
         return huntSzymanskiLCS(A, B);
    }
};
8785