# 792-number-of-matching-subsequences


Try it on <a href='https://leetcode.com/problems/792-number-of-matching-subsequences'>leetcode</a>

## Description
<div class="description">
<div><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>"ace"</code> is a subsequence of <code>"abcde"</code>.</li>
</ul>

<p>&nbsp;</p>
<p><strong>Example 1:</strong></p>

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

<p><strong>Example 2:</strong></p>

<pre><strong>Input:</strong> s = "dsahjpjauf", words = ["ahjpjau","ja","ahbwzgqnuk","tnmlanowax"]
<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>
</div>
</div>

## Solution(Python)
```Python
class Solution:
    def numMatchingSubseq(self, s: str, words: List[str]) -> int:
        return self.optimal(s, words)

    # Time Complexity: O(n*m)
    # space complexity: O(1)
    def naive(self, s: str, words: List[str]) -> int:
        cnt = 0

        def issubsequence(s, word):
            i = 0
            if len(word) > len(s):
                return False
            for c in s:
                if i < len(word) and word[i] == c:
                    i += 1
            return i == len(word)

        for word in words:
            if issubsequence(s, word):
                cnt += 1
        return cnt

    # Time Complexity: O(n*m)
    # space complexity: O(n)
    def better(self, s: str, words: List[str]) -> int:
        def issubseq(s, t):
            stack = []
            for i in t:
                stack.append(i)

            n = len(s)
            for i in range(n - 1, -1, -1):
                if not stack:
                    return True
                if stack[-1] == s[i]:
                    stack.pop()
            return stack == []

        hashmap = {}

        count = 0
        for word in words:
            if word not in hashmap:
                if issubseq(s, word):
                    count += 1
                    hashmap[word] = True
                else:
                    hashmap[word] = False
            else:
                if hashmap[word]:
                    count += 1
        return count

    # Time Complexity: O(nlogm)
    # space complexity: O(n)
    def optimal(self, s: str, words: List[str]) -> int:
        def issubseq(t):
            current_pos = -1
            stack = []
            for i in t:
                if indices[i]:
                    pos = bisect.bisect_right(indices[i], current_pos)
                    if pos == len(indices[i]):
                        return False
                    current_pos = indices[i][pos]
                else:
                    return False
            return True

        indices = defaultdict(list)
        for i, c in enumerate(s):
            indices[c].append(i)

        hashmap = {}

        count = 0
        for word in words:
            if word not in hashmap:
                if issubseq(word):
                    count += 1
                    hashmap[word] = True
                else:
                    hashmap[word] = False
            else:
                if hashmap[word]:
                    count += 1
        return count

```