class Solution:
    def numMatchingSubseq(self, S: str, words: List[str]) -> int:
        #Time Complexity: O(len(word) * len(words) * O(log len(S)))
        #Space Comlexity: O(len(S))

        Dict_S = {}

        for i, s in enumerate(S):
            if s not in Dict_S:
                Dict_S[s] = [i]
            else:
                Dict_S[s].append(i)

        res = 0


        Set_word = set()

        for word in words:

            if word in Set_word:
                res += 1
                continue



            if word[0] in Dict_S:
                S_loc = Dict_S[word[0]][0]
                word_loc = 1        

                while(word_loc < len(word)):

                    if word[word_loc] in Dict_S:
                        idx = bisect.bisect_right(Dict_S[word[word_loc]], S_loc)
                        if idx >= len(Dict_S[word[word_loc]]):
                            break
                        next_loc = Dict_S[word[word_loc]][idx]
                        S_loc = next_loc
                        word_loc += 1
                    else:
                        break

                if word_loc == len(word):
                    Set_word.add(word)
                    res += 1

        return res