792 - Number of Matching Subsequences

Difficulty: Medium | Pattern: String / Two Pointers | Company tags: Google, Amazon, Facebook

Problem Statement

Given a string s and an array of strings words, return the number of words[i] that is a subsequence of s.

Example 1:

Input: s = "abcde", words = ["a","bb","acd","ace"]
Output: 3  ("a", "acd", "ace" are subsequences)

Example 2:

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

Approach: Bucket Waiting — O(|s| + sum of word lengths)

Key insight: Group words by their current first character they're waiting for. Process s one character at a time, advancing all words waiting on that character.

from collections import defaultdict

def numMatchingSubseq(s: str, words: list[str]) -> int:
    # Each bucket holds (remaining_word, index_into_word)
    waiting = defaultdict(list)
    for word in words:
        waiting[word[0]].append((word, 1))
    
    result = 0
    
    for char in s:
        advance = waiting[char]
        del waiting[char]  # clear bucket for this char
        for word, i in advance:
            if i == len(word):
                result += 1
            else:
                waiting[word[i]].append((word, i + 1))
    
    return result

Dry Run

s = "abcde", words = ["a","bb","acd","ace"]

Initial buckets: a: [("a",1),("acd",1),("ace",1)]; b: [("bb",1)]

char	advance	updates
a	("a",1),("acd",1),("ace",1)	"a" done (result=1), "acd"→c bucket, "ace"→c bucket
b	("bb",1)	"bb"→b bucket (needs 2nd b)
c	("acd",1),("ace",1)	"acd"→d, "ace"→e
d	("acd",1)	"acd" done (result=2)
e	("ace",1)	"ace" done (result=3)

Result: 3 ✓

Why This Beats Naive?

Naive: O(|s| × total chars in words). Bucket: each character of each word is processed once → O(|s| + total word chars).

Complexity

• Time: O(|s| + sum of word lengths)
• Space: O(sum of word lengths)