507. Number of Matching Subsequences
Your function receives a lowercase string s and a list of lowercase strings words. Count how many entries of words are subsequences of s, and return that count.
A subsequence is obtained by deleting zero or more characters from s without reordering what remains — so "ace" is a subsequence of "abcde", while "aec" is not. Duplicate entries in words are counted individually each time they match.
Example 1:
Input: s = "abcde", words = ["a","bb","acd","ace"]
Output: 3
Explanation: "a", "acd" and "ace" can all be traced left-to-right through "abcde". "bb" cannot: s contains only one b.
Example 2:
Input: s = "dsahjpjauf", words = ["ahjpjau","ja","ahbwzgqnuk","tnmlanowax"]
Output: 2
Explanation: "ahjpjau" and "ja" appear in order inside s; the other two words need letters s never provides in the right sequence.
Constraints:
- 1 ≤ s.length ≤ 5 * 10⁴
- 1 ≤ m ≤ 5000
- 1 ≤ words[i].length ≤ 50
- s and every word contain only lowercase English letters
Hints:
Checking one word is a greedy two-pointer scan: walk s once and advance the word pointer on every match. That is O(m · |s|) overall — the waste is that s gets re-scanned from scratch for every single word. Can the words share one scan?
Group the words by the next letter each one is waiting for (26 buckets). Read s left to right: on character c, every word in bucket c advances one position — it either finishes (count it) or moves to the bucket of its new next letter. Alternative: precompute the sorted index list of every letter in s and binary-search each word's next jump.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: s = "abcde", words = ["a","bb","acd","ace"]
Expected output: 3