Number of Matching Subsequences

lcpy gen -n 792   # by problem number
lcpy gen -s number_of_matching_subsequences   # by problem name

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

Input: s = "dsahjpjauf", words = ["ahjpjau","ja","ahbwzgqnuk","tnmlanowax"]
Output: 2

from collections import defaultdict


class Solution:
    # Time: O(len(s) + total length of all words)
    # Space: O(len(words))

    def num_matching_subseq(self, s: str, words: list[str]) -> int:
        # Bucket words by the next character each one is waiting for.
        waiting: dict[str, list[tuple[int, int]]] = defaultdict(list)
        for idx, word in enumerate(words):
            waiting[word[0]].append((idx, 0))

        matched = 0
        for ch in s:
            for idx, pos in waiting.pop(ch, ()):
                nxt = pos + 1
                if nxt == len(words[idx]):
                    matched += 1
                else:
                    waiting[words[idx][nxt]].append((idx, nxt))
        return matched