<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 &a, string &b, int i, int j,vector<vector<int>> &dp){
//         int n = a.length();
//         int m = b.length();
//         if(j>=m || i>=n) {
//             return 0;
//         }
//         // else 
//         if(dp[i][j]!=-1){
//             return dp[i][j];
//         }
//         if(a[i]==b[j]){
//             // cout<<a[i]<<" "<<b[j]<<endl;
//             int ans = 1 + solve(a,b,i+1,j+1,dp);
//             dp[i][j]=ans;
//             return ans;
//         }
//         else {
//             return dp[i][j] = max(solve(a,b,i,j+1,dp), solve(a,b,i+1,j,dp));
//         }
//     }
//     int longestCommonSubsequence(string text1, string text2) {
//         vector<vector<int>> dp(text1.length(),vector<int>(text2.length(),-1));
//         return solve(text1,text2,0,0,dp);
//     }
// };

#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC optimize("no-math-errno,unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4")

constexpr uint MAX_SIZE = 1001;
std::array<uint, MAX_SIZE> dp{0}; // Global DP array, zero-initialized at program startup
std::uint32_t S[256][MAX_SIZE];

static int speedup = []() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    return 0;
}();

class Solution {
public:
    int longestCommonSubsequence(string X, string Y) {
        if ( X.size() < Y.size() ) swap(X,Y) ;
        int m = X.size() , n = Y.size();
        if (m == 0 || n == 0) return 0;
        int w = (m + 31) >> 5;

        //std::memset(S, 0, sizeof(std::uint32_t) * 256 * w);
        std::memset(S, 0, sizeof(std::uint32_t) * 256 * MAX_SIZE);
        std::int32_t set = 1;
        for (int i = 0, j = 0; i < m; ++i) {
            S[X[i]][j] |= set;
            set <<= 1;
            if (!set) set++,j++;
        }
        std::uint32_t L[w];
        std::memset(L, 0, sizeof(std::uint32_t) * w);
        for (int i = 0; i < n; ++i) {
            std::uint32_t b1 = 1;
            std::uint32_t b2 = 0;
            for (int j = 0; j < w; ++j) {
                std::uint32_t U  = L[j] | S[Y[i]][j];
                std::uint32_t c  = L[j] >> 31;
                std::uint32_t V  = U - (L[j] << 1 | b1+b2);
                b1 = c;
                b2 = (V > U);
                L[j] = U & (~V);
            }
        }      
        int res = 0;
        for (int i = 0; i < w; ++i)
            for (; L[i]; ++res)
                L[i] &= L[i] - 1;
        return res;
    }
};
8551