DIY: Number of Matching Subsequences

Solve the interview question "Number of Matching Subsequences" in this lesson.

Problem statement

Given a string, S, and a list of words, words, find the number of words[i] that are a subsequence of S.

Input

The input will be a string, S, and a list of strings, words. The following is an example input:

S = "abcde"
words = ["a", "bb", "acd", "ace"]

Output

The output will be the number of subsequences of S that exist in words. For the above input, the output will be:

3

The words "a", "acd", "ace" are subsequences of S, and their count is 3.

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.