Problem statement

https://binarysearch.com/problems/Subsequence-Match-Target/

Solution

Equal to Leetcode 0792. Number of Matching Subsequences.

Complexity

Time complexity is O(m*log n + n), because we do at most m binary searches and we need O(n) to evaluate places. Space complexity is O(n).

Code

class Solution:
    def solve(self, words, S):
        def isSubseq(word):
            curr = 0
            for symbol in word:
                ind = bisect_left(places[symbol], curr)
                if ind >= len(places[symbol]):
                    return False
                curr = places[symbol][ind] + 1
            
            return True
        
        places = defaultdict(list)
        for i, symbol in enumerate(S):
            places[symbol].append(i)
        
        return sum(isSubseq(word) for word in words)