<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>

# gaskdhjkdasfhgkljdhfkjahsdk
# ["dask"]
# g: [0, 13], a: [1, 9, 22], s: [2, 10, 24], k: [3, 7, 14, 20, 26], d: [4, 8, 17, 25], 
# h: [5, 12, 18, 23], j: [6, 16, 21], l: [15], f: [11, 19]

# "d" -> get the minimum index -> 4
# "a" -> get min index greater than 4 -> 9
# "s" -> get min index greater than 9 -> 10
# "k" -> get min index greater than 10 -> 14

# construct prefix tree from all `words`
# construct a map mapping each character in `s` to its positions
# traverse the prefix tree
#   at each node, keep track of the minimum index needed for the next character
#   get the available indices for the next character
#   binary search for the smallest number greater than the minimum index

from collections import Counter, defaultdict
from typing import Dict, List


class PrefixNode:
    def __init__(self, char: Optional[str] = None):
        self.char = char
        self.word = None
        self.children = dict()

    def get_child(self, c: str):
        return self.children.get(c)

    def set_child(self, c: str, other):
        self.children[c] = other


class Solver:
    def __init__(self, s: str, words: List[str]):
        self.char_index = self.create_char_index(s)
        self.root = self.create_prefix_tree(words)
        self.word_counts = Counter(words)
        self.visited = set()

    @staticmethod
    def create_char_index(s: str) -> Dict[str, List[int]]:
        index = defaultdict(list)
        for i, c in enumerate(s):
            index[c].append(i)
        return index

    @staticmethod
    def binary_search(nums: List[int], target: int) -> int:
        if len(nums) == 0 or target > nums[-1]:
            return -1
        if target <= nums[0]:
            return 0
        low = 0
        high = len(nums) - 1
        last_increased = False
        while low <= high:
            mid = low + (high - low) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                low = mid + 1
                last_increased = True
            else:
                high = mid - 1
                last_increased = False
        if last_increased:
            return mid + 1
        return mid

    def create_prefix_tree(self, words: List[str]):
        root = PrefixNode()
        for word in words:
            node = root
            for c in word:
                child = node.get_child(c)
                if child is None:
                    child = PrefixNode(c)
                    node.set_child(c, child)
                node = child
            node.word = word
        return root

    def traverse(self, node: PrefixNode, min_index: int):
        for char, child in node.children.items():
            indices = self.char_index.get(char, [])
            i = self.binary_search(indices, min_index)
            if i != -1:
                if child.word is not None:
                    self.visited.add(child.word)
                self.traverse(child, indices[i] + 1)

    def solve(self) -> int:
        self.traverse(self.root, min_index=0)
        print(self.visited)
        count = sum([self.word_counts[word] for word in self.visited])
        return count


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

30400