Number of Matching Subsequences - Video Solutions

Problem Overview: You are given a string s and an array of words. The task is to count how many of those words are subsequences of s. A word is a subsequence if its characters appear in the same order inside s, though not necessarily contiguously.

Approach 1: Brute Force Subsequence Check (Time: O(W * |s|), Space: O(1))

The straightforward approach checks every word individually against the main string. For each word, run a two-pointer scan: one pointer moves through s, the other through the word. When characters match, advance both pointers; otherwise only move the pointer in s. If the word pointer reaches the end, the word is a valid subsequence. This solution uses simple iteration over a string and requires no additional data structures. The downside is repeated scans of s for every word, which becomes expensive when the word list is large.

Approach 2: Efficient Group Matching Using Buckets (Time: O(|s| + total characters in words), Space: O(W))

A more scalable strategy processes all words simultaneously. Create 26 buckets (or a hash table) where each bucket stores iterators of words waiting for a specific character. Initially, place every word in the bucket corresponding to its first character. Then iterate through s. For each character c, take the list of words waiting for c, advance their pointer to the next character, and move them to the bucket of the next required character. If advancing reaches the end of the word, you found a valid subsequence. Each character of each word moves between buckets only once, which keeps the overall work proportional to the total length of all words.

This bucket technique behaves like a streaming matcher. Instead of scanning s repeatedly, the algorithm processes it once and lets words "react" when their needed character appears. The idea is similar to grouping tasks in an array of queues where each queue represents the next required character. This reduces redundant work and handles large input efficiently.

Recommended for interviews: Interviewers typically expect the bucket-based grouping approach. The brute force solution shows you understand how subsequences work, but it does not scale when thousands of words must be checked. The bucket strategy demonstrates stronger algorithmic thinking because it transforms repeated scans into a single pass over s while incrementally advancing every candidate word.