<p>Given a string <code>s</code> and an array of strings <code>words</code>, return <em>the number of</em> <code>words[i]</code> <em>that is a subsequence of</em> <code>s</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>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;abcde&quot;, words = [&quot;a&quot;,&quot;bb&quot;,&quot;acd&quot;,&quot;ace&quot;]
<strong>Output:</strong> 3
<strong>Explanation:</strong> There are three strings in words that are a subsequence of s: &quot;a&quot;, &quot;acd&quot;, &quot;ace&quot;.
</pre>

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

<pre>
<strong>Input:</strong> s = &quot;dsahjpjauf&quot;, words = [&quot;ahjpjau&quot;,&quot;ja&quot;,&quot;ahbwzgqnuk&quot;,&quot;tnmlanowax&quot;]
<strong>Output:</strong> 2
</pre>

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

<ul>
	<li><code>1 &lt;= s.length &lt;= 5 * 10<sup>4</sup></code></li>
	<li><code>1 &lt;= words.length &lt;= 5000</code></li>
	<li><code>1 &lt;= words[i].length &lt;= 50</code></li>
	<li><code>s</code> and <code>words[i]</code> consist of only lowercase English letters.</li>
</ul>

class Solution:
    
    def numMatchingSubseq(self, s: str, words: List[str]) -> int:

        is_sub = {}

        def dp(w, i, j):

            if j == -1:
                is_sub[w] = True
                return True

            if i == -1:
                is_sub[w] = False
                return False

            if s[i] == w[j]:
                return dp(w, i-1, j-1)

            return dp(w, i-1, j)

        count = 0 
        ns = len(s)

        for w in words:

            if w in is_sub:
                if is_sub[w]: 
                    count += 1
                continue

            dp(w, ns-1, len(w)-1)

            if is_sub[w]:    
                count += 1

        return count

    # use dp[i][j]
    #    true if word[0:j] is subsequence of s[0:i]
    #    dp[i][j] =  dp[i-1][j-1] if s[i] == w[j]   or
    #                dp[i-1][j] otherwise
    #    dp[i][-1] = True
    #    dp[-1][j] = False
    #
    # Better, improve 3sec!
    #    but still beats only 5%
    # 
    def numMatchingSubseq_DP(self, s: str, words: List[str]) -> int:

        @cache
        def dp(w, i, j):

            if j == -1:
                return True

            if i == -1:
                return False

            if s[i] == w[j]:
                return dp(w, i-1, j-1)

            return dp(w, i-1, j)

        count = 0 
        ns = len(s)
        prev = {}

        for w in words:

            if w in prev:
                if prev[w]: 
                    count += 1
                continue

            w_is_sub = dp(w, ns-1, len(w)-1)

            if w_is_sub:    
                count += 1

            prev[w] = w_is_sub
            dp.cache_clear()

        return count
    

    # FIRST IDEA
    #   AC! but beats only 5%
    #   mark positions and memoize
    #   copy deques everytime
    #   
    def numMatchingSubseq_FIRST(self, s: str, words: List[str]) -> int:
        
        pos_orig = defaultdict(deque)

        for i, c in enumerate(s):
            pos_orig[c].append(i)

        def copy(x):
            c = x.copy()
            for k, v in x.items():
                c[k] = v.copy()
                  
            return c

        @cache
        def isSub(w):
            pos = copy(pos_orig)
            curr_pos = -1

            for c in w:

                while pos[c] and pos[c][0] < curr_pos:
                    pos[c].popleft()

                if not pos[c]:
                    # print(f'{w} -> False (c={c}), {pos[c]} vs {curr_pos}')
                    return False

                curr_pos = pos[c][0]
                # print(f'  {w} Found c={c}, {pos[c]} vs {curr_pos}')
                pos[c].popleft()                
            
            # print(w, '-> True,')
            return True

        return len([x for x in words if isSub(x)])

31900