<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 {
    vector<int> memo;
    int memoStride;
    
    void memoReset(int size1, int size2) {
        memoStride = size1 + 1;
        memo.resize((size1 + 1) * (size2 + 1), -1);
    }
    int memoSet(int size1, int size2, int value)    { return memo[memoStride * size2 + size1] = value; }
    int memoGet(int size1, int size2)               { return memo[memoStride * size2 + size1]; }

public:
    int longestCommonSubsequence(string text1, string text2) {
        memoReset(text1.size(), text2.size());
        return longestCommonSubsequence(text1.c_str(), text1.size(), text2.c_str(), text2.size());
    }
    int longestCommonSubsequence(const char* t1, int s1, const char* t2, int s2) {
        int res = memoGet(s1, s2);        
        if(res >= 0)
            return res;

        if(s1 == 0 || s2 == 0)
            res = 0;
        else if(t1[s1-1] == t2[s2-1])
            res = longestCommonSubsequence(t1, s1 - 1, t2, s2 - 1) + 1;
        else {
            int s1s = s1 - 1, s2s = s2 - 1;
            while(s1s > 0 && t1[s1s - 1] == t1[s1s]) --s1s;
            while(s2s > 0 && t2[s2s - 1] == t2[s2s]) --s2s;
            res = max(longestCommonSubsequence(t1, s1, t2, s2s), longestCommonSubsequence(t1, s1s, t2, s2));
        }

        return memoSet(s1, s2, res);
    }
};
21641