<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:
        """
        s = "abcde
        words = ["a", "bb", "acd", "ace"]

        sub_seq = 3 -> int

        thoughts:
        simple method would be to check for every word in words is subseq of s

        e.g. for "abcde"
               "a" 
               "a" == "a" -> yes, we are done -> increment counter by 1
        e.g. for word = "bb" :

            "b" == "a" -> no, move to 2nd character in s
            "b" == "b" -> yes, move to 2nd character in word and s 
            "b" == "c" -> no, move to 2nd character in s..
            so.. on after we are done, can't find "b" == any other character in s

            repeat same with acd, ace

            if len(words) = M
            max(len(word) in words) = N
            len(s) = L
            Then complexity is O(MNL)

            One way to optimize this is before looping for every word, we check the length of 
            word in words <= s, otherwise move forward
            
            Another optimization we could do is even while looping through each word, we check
            that the remaining characters in word are less than that in s

        """
        num_subseq = 0
        # self.s = s
        # self.sub_sq = dict()

        lookup = defaultdict(list)
        for index, chr in enumerate(s):
                lookup[chr].append(index)

        print(lookup)

        
        def binary_search(ind, list_chr):
            start, end = 0, len(list_chr)
            while start < end:
                mid = start + (end - start)//2
                if list_chr[mid] > ind:
                    end = mid
                
                else:
                    start = mid+1

            return start
        
        for word in words:
            # print(wird)
            found = True
            prev = -1
            for chr in word:
                
                    update = binary_search(prev, lookup[chr])
                    if update == len(lookup[chr]):
                        found  = False
                        # self.sub_sq[word] = False
                        break
                    else:
                        prev = lookup[chr][update]

                # self.sub_sq[word] = True
            if found:num_subseq+=1
            
            # elif self.sub_sq[word] == True: num_subseq+=1

                    

        return num_subseq




        # def find_subseq(word):
        #     len_word = len(word)
        #     len_s = len(self.s)
        #     if len_word > len_s:return False
        #     j = 0

        #     for i in range(len_s):
        #         if (len_word - j) > (len_s - i): return False
        #         # print(word, i , j, len_word)

        #         if j == len_word: return True

        #         if self.s[i] == word[j]:
        #             j+=1
        #             continue

        #     if j != len_word: return False
        #     return True


        
        
21200