We need to count how many words from the array are subsequences of the string s. A subsequence means we can find the word's characters in s in order, but they don't need to be contiguous. For instance, "acd" is a subsequence of "abcde" because we can pick 'a' at index 0, 'c' at index 2, and 'd' at index 3.

The brute force idea is to check each word independently: for each word, scan through s with two pointers to test whether it's a subsequence. The constraints make this expensive. With up to 5000 words and s up to 50,000 characters long, we might scan through s 5000 times.

The way out is to stop re-reading s for every word. We can either scan s once while advancing all words in parallel (the bucket approach), or precompute where each character appears in s so that checking any word becomes a series of fast lookups (the binary search approach).

Key Constraints:

Intuition

Check each word against s using the two-pointer technique. Start a pointer at the beginning of s and a pointer at the beginning of the word. Walk through s, and whenever the current character matches the word's current character, advance the word pointer. If the word pointer reaches the end of the word, the word is a subsequence.

This works because the two-pointer scan is greedy: matching each word character at the earliest possible position in s never blocks a later character that a different choice would have allowed. Any valid match could only have used a position at or after the one we picked.

Algorithm

Example Walkthrough

Code

The bottleneck is that we scan the entire string s independently for every word. With 5000 words, we walk through s 5000 times. The next approach scans s exactly once and advances every word as it goes.

Intuition

Instead of taking each word and checking it against s, flip the perspective. Scan through s one character at a time, and for each character, advance every word that is currently waiting for that character.

The structure is 26 waiting lists, one per lowercase letter. Each word sits in the list for its next needed character. When we read a character in s, we take everyone from that list, advance their pointer by one, and either count them as done (if they have matched all their characters) or move them to the list for their new next character.

This scans s exactly once, and each character of each word is processed exactly once when its word advances through a list.

Algorithm

Example Walkthrough

Code

The bucket approach runs in O(m + T) and processes all words together. The next approach takes a different route: it preprocesses s into an index that answers "where does character X next appear after position P?" with a single binary search, so each word can be checked independently without rescanning s.

Intuition

Before looking at any word, preprocess s by recording where each character appears. For s = "abcde", 'a' appears at position [0], 'b' at [1], 'c' at [2], and so on. For s = "abacd", 'a' appears at positions [0, 2]. Because we record positions in increasing order, each character's list is already sorted.

To check if a word is a subsequence, we no longer scan s. For the first character of the word, take the earliest position where it occurs. For the second character, find the first position that comes after the one we used. For the third character, find the first position after that, and so on. Each "find the next position after X" query is a binary search on that character's sorted position list. Taking the earliest valid position each time is the same greedy choice that made the two-pointer scan correct, so it never rules out a match that exists.

If at any point we can't find a valid position (there's no occurrence of the needed character after our current position), the word is not a subsequence.

Algorithm

Example Walkthrough

Code