DSA problem
Number of Matching Subsequences
Given a string s and an array of strings words, return the number of words[i] that is a subsequence of s.
A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.
For example, "ace" is a subsequence of "abcde".
A naive solution checks each word independently against s, which is too slow when there are many long words. The challenge is to process all words together in a single sweep over s.
Examples
Example 1
Input:
s = "abcde", words = ["a","bb","acd","ace"]Output:
3Explanation: There are three matching subsequences: "a", "acd", and "ace". The word "bb" is not a subsequence because s contains only one "b".
Example 2
Input:
s = "dsahjpjauf", words = ["ahjpjau","ja","ahbwzgqnuc"]Output:
2Explanation: The words "ahjpjau" and "ja" are subsequences of s. The word "ahbwzgqnuc" is not.
Example 3
Input:
s = "abc", words = ["abc","abcd",""]Output:
2Explanation: The empty string is a subsequence of any string, and "abc" matches exactly. "abcd" cannot match because s has no "d".
Constraints
- 1 <= s.length <= 5 * 10^4
- 1 <= words.length <= 5000
- 1 <= words[i].length <= 50
- s and words[i] consist of only lowercase English letters.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.