Number of Matching Subsequences

Number of Matching Subsequences

What is this problem about?

The Number of Matching Subsequences problem gives you a string word and a list of strings words. For each string in words, determine whether it is a subsequence of word. Return how many strings in words are subsequences of word. The naive O(n*k) approach (check each word one by one) is too slow for large inputs. This coding problem tests efficient multi-pattern subsequence matching.

Why is this asked in interviews?

Apple, Uber, Meta, Salesforce, Amazon, and Google ask this because it tests the ability to batch-process multiple queries against a single string. The efficient solution groups words by their current expected character and advances them in waves. The array, hash table, sorting, trie, binary search, string, and dynamic programming interview pattern is all applicable.

Algorithmic pattern used

Bucket-by-current-character approach. Create 26 buckets (one per character). Place each word's iterator (word, index) in the bucket of its current needed character. Process the string word left to right. For each character c, process all iterators in bucket[c]: advance each iterator to the next needed character. If the iterator exhausted (fully matched), increment the count. Move the iterator to its new bucket.

Example explanation

word = "abcde", words = ["ace","bc","e"].

• Buckets: a→["ace"@0, "bc" skips a], b→["bc"@0], e→["e"@0].
• Process 'a': advance "ace" → now needs 'c'. Move to c-bucket.
• Process 'b': advance "bc" → now needs 'c'. Move to c-bucket.
• Process 'c': advance "ace" → needs 'e'. Move to e-bucket. Advance "bc" → exhausted. Count=1.
• Process 'e': advance "ace" → exhausted. Count=2. Advance "e" → exhausted. Count=3. Answer = 3.

Common mistakes candidates make

• Checking each word independently (O(n * sum_of_word_lengths), too slow).
• Not using iterators/indices — storing words by their entire remaining suffix.
• Processing buckets in the wrong order (must process character c when reading word[i]=c).
• Not handling duplicate words in words (count each separately).

Interview preparation tip

The bucket-by-current-character approach is elegant and O(n + sum_of_lengths). Practice this pattern for multi-pattern matching problems. An alternative: precompute nextPos[c][i] = next position of character c at or after position i in word. Then binary search for each character in each word. Both approaches demonstrate O(n log n) or O(n) mastery of string processing patterns.