Number of Matching Subsequences
Medium · Strings · Array · Hash Table · String · Binary Search · Trie · Sorting
Problem
Given a string s and a list of strings words, return how many of the words are a subsequence of s.
A subsequence keeps some of the letters of s — any number may be left out — in their original order: "ace" is a subsequence of "abcde", but "aec" is not. Each entry of words counts on its own, so a word that appears twice and matches counts twice.
Examples
Input: s = "abcde", words = ["a","bb","acd","ace"] Output: 3
"a", "acd" and "ace" appear in order. "bb" needs two b’s and s has only one.
Input: s = "dsahjpjauf", words = ["ahjpjau","ja","ahbwzgqnuk","tnmlanowax"] Output: 2
"ahjpjau" and "ja" match. The other two use letters that s does not have.
Constraints
- 1 <= len(s) <= 5 * 10^4
- 1 <= len(words) <= 5000
- 1 <= len(words[i]) <= 50
- s and words[i] consist of lowercase English letters
Approaches
- Check each word with two pointers — time O(len(words) · |s|), space O(1)
Related problems
Start free on Cariara · Coding problems · System design studio
