Number of Matching Subsequences

MediumStringshashing

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given a string s and an array of strings words. A word is a *subsequence* of s if it can be obtained by deleting zero or more characters from s without reordering the rest. Return how many entries of words are subsequences of s. Duplicate words are counted once per occurrence in words. Checking each word independently with two pointers costs O(len(s)) per word; aim to process all words in a single pass over s (for example by bucketing words by the next character they are waiting for).

Examples

Input: s = "bcaxd", words = ["ba","cd","xb","bcd","d"]
Output: 4
"ba", "cd", "bcd" and "d" appear in order; "xb" does not because no b follows the x.
Input: s = "aaa", words = ["aa","aaaa","b"]
Output: 1
Only "aa" fits; "aaaa" needs four a's.

Constraints

  • 1 <= s.length <= 5 * 10^4
  • 1 <= words.length <= 5000
  • 1 <= words[i].length <= 50
  • `s` and `words[i]` contain only lowercase English letters

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More hashing problems