Number of Matching Subsequences
Description
You get a string s and an array of strings words.
Return how many of the words are subsequences of s. A subsequence is what's left after deleting some letters (possibly none) without changing the order of the rest: "ace" is a subsequence of "abcde". Words can repeat, and every copy counts.
Examples
Example 1
Input: s = "abcde", words = ["a", "bb", "acd", "ace"]
Output: 3
Explanation: a, acd and ace can be made by deleting letters; bb needs two b's and s has one.
Example 2
Input: s = "dsahjpjauf", words = ["ahjpjau", "ja", "ahbwzgqnuk", "tnmlanowax"]
Output: 2
Explanation: ahjpjau and ja are subsequences; the other two have letters s doesn't.
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.
Editorial
Brute Force
Intuition
Check each word on its own, the way Is Subsequence does: walk s from the start, and move to the word's next letter whenever s shows the one you're waiting for. If every letter of the word is matched, count it.
Step-by-Step Explanation
Let's check each word against s = "abcde":
- Walk s for "a". Its letters turn up in order at 0, so it's a subsequence. That's 1 so far.
- Walk s for "bb". Only 1 of its 2 letters turn up in order, so it isn't one. Still 1.
- Walk s for "acd". Its letters turn up in order at 0, 2, 3, so it's a subsequence. That's 2 so far.
- Walk s for "ace". Its letters turn up in order at 0, 2, 4, so it's a subsequence. That's 3 so far.
The answer is 3.
Walk s Once per Word — The row is s. Each step walks it for one word, marking where that word's letters were matched.
Algorithm
- For each word: walk
swith a pointer into the word, advancing it on every match. - If the pointer reaches the end of the word, count it.
Code
class Solution {
public:
int numMatchingSubseq(string s, vector<string>& words) {
int count = 0;
for (const string& w : words) {
size_t k = 0;
for (size_t i = 0; i < s.size() && k < w.size(); i++) // walk s, matching w's letters in order
if (s[i] == w[k]) k++;
if (k == w.size()) count++;
}
return count;
}
};
class Solution:
def numMatchingSubseq(self, s: str, words: list[str]) -> int:
count = 0
for w in words:
k = 0
for c in s: # walk s, matching w's letters in order
if c == w[k]:
k += 1
if k == len(w):
break
if k == len(w):
count += 1
return count
class Solution {
public int numMatchingSubseq(String s, String[] words) {
int count = 0;
for (String w : words) {
int k = 0;
for (int i = 0; i < s.length() && k < w.length(); i++) // walk s, matching w's letters in order
if (s.charAt(i) == w.charAt(k)) k++;
if (k == w.length()) count++;
}
return count;
}
}
var numMatchingSubseq = function(s, words) {
let count = 0;
for (const w of words) {
let k = 0;
for (let i = 0; i < s.length && k < w.length; i++) // walk s, matching w's letters in order
if (s[i] === w[k]) k++;
if (k === w.length) count++;
}
return count;
};
Complexity Analysis
Time Complexity: O(|words| · |s|)
A word that isn't a subsequence, or whose last letter comes late, walks all of s.
Space Complexity: O(1)
Why This Approach Is Not Efficient
5000 words times 5 × 10^4 letters is 2.5 × 10^8 steps (over the time limit in Python).
Every word walks s from the start again. Turn it around: walk s once, and at each letter, move forward exactly the words that were waiting for that letter.
Optimal Approach - Words Waiting on the Next Letter
Intuition
Keep 26 lists, one per letter. A word sits in the list of the next letter it needs. Walk s once: at each letter c, take the whole list for c out, and move each word in it one letter on. A word that has no letters left is a subsequence; any other word joins the list of its next letter.
Take the list out before refilling: a word like "bb" moves from the b list back into the b list, and it must wait for the next b of s, not use this one twice.
It's a hash table whose keys are letters and whose values are lists of words.
Step-by-Step Explanation
Let's walk s = "abcde" once:
- File every word under its first letter. The value word@m means m letters of it are matched.
- s gives a. "a" is complete; "acd" now waits for c; "ace" now waits for c. Done so far, 1.
- s gives b. "bb" now waits for b. Done so far, 1.
- s gives c. "acd" now waits for d; "ace" now waits for e. Done so far, 1.
- s gives d. "acd" is complete. Done so far, 2.
- s gives e. "ace" is complete. Done so far, 3.
The answer is 3.
Wake the Words Waiting on Each Letter — The row is s; the table lists the words waiting on each letter (word@m: m letters matched).
Algorithm
- Make 26 empty lists; put each word, with 0 letters matched, in the list of its first letter.
- For each letter
cofs: take out the list forc. For each word in it: if this was its last letter, count it; otherwise put it in the list of its next letter. - Return the count.
Code
class Solution {
public:
int numMatchingSubseq(string s, vector<string>& words) {
vector<vector<pair<int, int>>> waiting(26); // next letter needed -> {word index, letters matched}
for (int i = 0; i < (int)words.size(); i++) waiting[words[i][0] - 'a'].push_back({i, 0});
int done = 0;
for (char c : s) {
vector<pair<int, int>> ready;
swap(ready, waiting[c - 'a']); // take this letter's list before refilling it
for (auto [i, m] : ready) {
if (m + 1 == (int)words[i].size()) done++; // the whole word is matched
else waiting[words[i][m + 1] - 'a'].push_back({i, m + 1});
}
}
return done;
}
};
class Solution:
def numMatchingSubseq(self, s: str, words: list[str]) -> int:
waiting = [[] for _ in range(26)] # next letter needed -> (word, letters matched so far)
for w in words:
waiting[ord(w[0]) - ord('a')].append((w, 0))
done = 0
for c in s:
k = ord(c) - ord('a')
ready, waiting[k] = waiting[k], [] # take this letter's list before refilling it
for w, m in ready:
if m + 1 == len(w):
done += 1 # the whole word is matched
else:
waiting[ord(w[m + 1]) - ord('a')].append((w, m + 1))
return done
class Solution {
public int numMatchingSubseq(String s, String[] words) {
List<List<int[]>> waiting = new ArrayList<>(); // next letter needed -> {word index, letters matched}
for (int k = 0; k < 26; k++) waiting.add(new ArrayList<>());
for (int i = 0; i < words.length; i++) waiting.get(words[i].charAt(0) - 'a').add(new int[]{i, 0});
int done = 0;
for (char c : s.toCharArray()) {
List<int[]> ready = waiting.get(c - 'a');
waiting.set(c - 'a', new ArrayList<>()); // take this letter's list before refilling it
for (int[] e : ready) {
String w = words[e[0]];
if (e[1] + 1 == w.length()) done++; // the whole word is matched
else waiting.get(w.charAt(e[1] + 1) - 'a').add(new int[]{e[0], e[1] + 1});
}
}
return done;
}
}
var numMatchingSubseq = function(s, words) {
let waiting = Array.from({ length: 26 }, () => []); // next letter needed -> [word, letters matched]
for (const w of words) waiting[w.charCodeAt(0) - 97].push([w, 0]);
let done = 0;
for (const c of s) {
const k = c.charCodeAt(0) - 97;
const ready = waiting[k];
waiting[k] = []; // take this letter's list before refilling it
for (const [w, m] of ready) {
if (m + 1 === w.length) done++; // the whole word is matched
else waiting[w.charCodeAt(m + 1) - 97].push([w, m + 1]);
}
}
return done;
};
Complexity Analysis
Time Complexity: O(|s| + total length of the words)
Each letter of s is visited once, and each letter of each word moves its word once.
Space Complexity: O(|words|) for the lists
Common Mistakes
Each of these looks right on a quick read, and the tests still reject it. The outputs below come from running the code.
Refilling the list you're reading. ready = waiting[k] # and then appending to waiting[k] while walking ready
On s = "abcde", words = ["a", "bb", "acd", "ace"], it returns 4; the answer is 3. Walking waiting[c] while appending to it lets a word whose next letter is c again (the second b of "bb") move on with the same letter of s. Take the list out first, then refill it.
Counting each distinct word once. for w in set(words):
On s = "a", words = ["a", "a", "a"], it returns 1; the answer is 3. Words can repeat, and every copy counts. Turning the list into a set first throws the copies away.
Checking the letters, not the order. all(c in set(s) for c in w)
On s = "abc", words = ["cb", "ba", "ca", "abc"], it returns 4; the answer is 1. A subsequence keeps the order: "cb" isn't a subsequence of "abc" even though both letters are there.
Where This Pattern Is Taught
This problem practises a hash table of waiting lists, keyed by what each item needs next. It's taught in Frequency Counting with Hash Maps.