Number of Matching Subsequences
Number of Matching Subsequences is a medium arrays & hashing problem solved with the hashing pattern.
The best approach, optimal (buckets of waiting words), runs in O(|s| + T) time and O(W) space.
Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force (two pointers per word) up.
Problem
You are given a string s and an array of strings words. Count how many of the words are subsequences of s.
A word is a subsequence of s if you can obtain it by deleting zero or more characters from s without changing the order of the characters that remain. For example, "pat" is a subsequence of "planet", but "tan" is not. Every entry of words is counted on its own, even if the same word appears several times.
Examples
Example 1
- Input
s = "planet", words = ["pat", "lane", "net", "ten", "p"]- Output
4- Why
- "pat", "lane", "net" and "p" can be read from s left to right; "ten" cannot, because the only 'e' in s comes before the 't'.
Example 2
- Input
s = "xyz", words = ["xz", "zy", "xyz", "xyzz"]- Output
2- Why
- "xz" and "xyz" match. "zy" has the letters in the wrong order and "xyzz" needs two z's.
Example 3
- Input
s = "aab", words = ["ab", "ab", "ba"]- Output
2- Why
- Each copy of a repeated word is counted separately, so "ab" counts twice.
Constraints
1 <= s.length <= 5 * 10^41 <= words.length <= 50001 <= words[i].length <= 50sand everywords[i]consist of lowercase English letters.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 10 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (two pointers per word) | O(W · (|s| + L)) | O(1) |
| Better (positions per letter + binary search) | O(|s| + T · log |s|) | O(|s|) |
| Optimal (buckets of waiting words) | O(|s| + T) | O(W) |
1Brute force (two pointers per word)
O(W · (|s| + L))Every one of the W words may scan the whole of s (and its own L letters).O(1)Only two pointers and a counter.Check each word on its own: walk through s with one pointer and through the word with another, advancing the word pointer whenever the characters match. The word is a subsequence if its pointer reaches the end.
- count = 0.
- For each word: j = 0; for each character of s, if j < word.length and it equals word[j], j++.
- If j == word.length, count++.
class Solution {
public int numMatchingSubseq(String s, String[] words) {
int count = 0;
for (String w : words) {
int j = 0;
for (int i = 0; i < s.length() && j < w.length(); i++) {
if (s.charAt(i) == w.charAt(j)) j++;
}
if (j == w.length()) count++;
}
return count;
}
}class Solution:
def numMatchingSubseq(self, s: str, words: List[str]) -> int:
count = 0
for w in words:
j = 0
for c in s:
if j < len(w) and c == w[j]:
j += 1
if j == len(w):
count += 1
return countclass Solution {
public:
int numMatchingSubseq(string s, vector<string>& words) {
int count = 0;
for (const string& w : words) {
size_t j = 0;
for (size_t i = 0; i < s.size() && j < w.size(); i++) {
if (s[i] == w[j]) j++;
}
if (j == w.size()) count++;
}
return count;
}
};function numMatchingSubseq(s, words) {
let count = 0;
for (const w of words) {
let j = 0;
for (let i = 0; i < s.length && j < w.length; i++) {
if (s[i] === w[j]) j++;
}
if (j === w.length) count++;
}
return count;
}2Better (positions per letter + binary search)
O(|s| + T · log |s|)Building the lists is one pass over s; each of the T letters across all words costs one binary search.O(|s|)The position lists together store every index of s once.Pre-process s once: for each letter keep the sorted list of indices where it occurs. To match a word, keep the index prev of the last matched character and, for the next letter, binary-search its list for the first index greater than prev. If there is none, the word fails.
- pos[c] = sorted indices of letter c in s.
- For each word: prev = -1; for each letter c, find the first index in pos[c] that is > prev; if none, the word fails, else prev = that index.
- Count the words that never fail.
class Solution {
public int numMatchingSubseq(String s, String[] words) {
List<List<Integer>> pos = new ArrayList<>();
for (int c = 0; c < 26; c++) pos.add(new ArrayList<>());
for (int i = 0; i < s.length(); i++) pos.get(s.charAt(i) - 'a').add(i);
int count = 0;
for (String w : words) {
int prev = -1;
boolean ok = true;
for (int k = 0; k < w.length() && ok; k++) {
List<Integer> list = pos.get(w.charAt(k) - 'a');
int lo = 0, hi = list.size(); // first index with list[idx] > prev
while (lo < hi) {
int mid = (lo + hi) >>> 1;
if (list.get(mid) > prev) hi = mid;
else lo = mid + 1;
}
if (lo == list.size()) ok = false;
else prev = list.get(lo);
}
if (ok) count++;
}
return count;
}
}class Solution:
def numMatchingSubseq(self, s: str, words: List[str]) -> int:
pos = defaultdict(list)
for i, c in enumerate(s):
pos[c].append(i)
count = 0
for w in words:
prev = -1
ok = True
for c in w:
lst = pos[c]
k = bisect.bisect_right(lst, prev)
if k == len(lst):
ok = False
break
prev = lst[k]
if ok:
count += 1
return countclass Solution {
public:
int numMatchingSubseq(string s, vector<string>& words) {
vector<vector<int>> pos(26);
for (int i = 0; i < (int)s.size(); i++) pos[s[i] - 'a'].push_back(i);
int count = 0;
for (const string& w : words) {
int prev = -1;
bool ok = true;
for (char c : w) {
const vector<int>& list = pos[c - 'a'];
auto it = upper_bound(list.begin(), list.end(), prev);
if (it == list.end()) { ok = false; break; }
prev = *it;
}
if (ok) count++;
}
return count;
}
};function numMatchingSubseq(s, words) {
const pos = Array.from({ length: 26 }, () => []);
for (let i = 0; i < s.length; i++) pos[s.charCodeAt(i) - 97].push(i);
let count = 0;
for (const w of words) {
let prev = -1;
let ok = true;
for (let k = 0; k < w.length && ok; k++) {
const list = pos[w.charCodeAt(k) - 97];
let lo = 0, hi = list.length; // first index with list[idx] > prev
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (list[mid] > prev) hi = mid;
else lo = mid + 1;
}
if (lo === list.length) ok = false;
else prev = list[lo];
}
if (ok) count++;
}
return count;
}3Optimal (buckets of waiting words)
O(|s| + T)The scan over s is linear, and each letter of each word causes exactly one move between buckets, so T letters in total cost O(T).O(W)Every word sits in exactly one bucket at a time.Scan s exactly once and move all words forward together. Each word is represented by (word index, position of the next letter it needs), and it waits in the bucket of that letter. When the scan reads letter c, empty bucket c: every word in it advances by one; a word that has used all its letters is counted, the others move to the bucket of their next needed letter. A word that needs c again goes into the fresh bucket c and waits for a later c.
- buckets = 26 empty lists; put (i, 0) into the bucket of words[i][0] for every word.
- For each character c of s: take the list in bucket c and replace it with an empty list.
- For each (i, p) in the taken list: p++; if p == words[i].length, count++; else add (i, p) to the bucket of words[i][p].
- Return count.
class Solution {
public int numMatchingSubseq(String s, String[] words) {
List<List<int[]>> buckets = new ArrayList<>();
for (int c = 0; c < 26; c++) buckets.add(new ArrayList<>());
for (int i = 0; i < words.length; i++) {
buckets.get(words[i].charAt(0) - 'a').add(new int[] { i, 0 });
}
int count = 0;
for (int k = 0; k < s.length(); k++) {
int c = s.charAt(k) - 'a';
List<int[]> waiting = buckets.get(c);
buckets.set(c, new ArrayList<>());
for (int[] item : waiting) {
String w = words[item[0]];
int p = item[1] + 1;
if (p == w.length()) {
count++;
} else {
item[1] = p;
buckets.get(w.charAt(p) - 'a').add(item);
}
}
}
return count;
}
}class Solution:
def numMatchingSubseq(self, s: str, words: List[str]) -> int:
buckets = defaultdict(list)
for i, w in enumerate(words):
buckets[w[0]].append((i, 0))
count = 0
for c in s:
waiting = buckets[c]
buckets[c] = []
for i, p in waiting:
p += 1
w = words[i]
if p == len(w):
count += 1
else:
buckets[w[p]].append((i, p))
return countclass Solution {
public:
int numMatchingSubseq(string s, vector<string>& words) {
vector<vector<pair<int, int>>> buckets(26);
for (int i = 0; i < (int)words.size(); i++) buckets[words[i][0] - 'a'].push_back({i, 0});
int count = 0;
for (char ch : s) {
int c = ch - 'a';
vector<pair<int, int>> waiting;
waiting.swap(buckets[c]);
for (auto [i, p] : waiting) {
p++;
const string& w = words[i];
if (p == (int)w.size()) count++;
else buckets[w[p] - 'a'].push_back({i, p});
}
}
return count;
}
};function numMatchingSubseq(s, words) {
let buckets = Array.from({ length: 26 }, () => []);
words.forEach((w, i) => buckets[w.charCodeAt(0) - 97].push([i, 0]));
let count = 0;
for (let k = 0; k < s.length; k++) {
const c = s.charCodeAt(k) - 97;
const waiting = buckets[c];
buckets[c] = [];
for (const [i, p0] of waiting) {
const p = p0 + 1;
const w = words[i];
if (p === w.length) count++;
else buckets[w.charCodeAt(p) - 97].push([i, p]);
}
}
return count;
}Edge cases to test
- A word longer than s
- A word equal to s
- Repeated words in the list (each one counts)
- Words needing the same letter several times in a row, like "aaa"
- Letters of a word that never appear in s
Hints
Hint 1
Checking one word is a two-pointer scan over s. Why is doing that for every word too slow when s is long?
Hint 2
For each letter, store the sorted list of positions where it occurs in s. Then each next letter of a word can be found with a binary search for the first position after the current one.
Hint 3
Even better: scan s only once. Keep 26 buckets of words waiting for a particular letter; when you read that letter in s, every word in its bucket advances to its next letter (or is complete).
FAQ
What is the best time complexity for Number of Matching Subsequences?
Optimal (buckets of waiting words) runs in O(|s| + T) time and O(W) extra space. The scan over s is linear, and each letter of each word causes exactly one move between buckets, so T letters in total cost O(T).
Which pattern does Number of Matching Subsequences use?
It is a arrays & hashing problem that uses the hashing pattern. Other problems with the same pattern: Group Anagrams, First Unique Character in a String, Group Shifted Strings.
Is there a brute force solution for Number of Matching Subsequences?
Yes. Brute force (two pointers per word) takes O(W · (|s| + L)) time and O(1) space. Check each word on its own: walk through s with one pointer and through the word with another, advancing the word pointer whenever the characters match.
Which edge cases should I test for Number of Matching Subsequences?
A word longer than s; A word equal to s; Repeated words in the list (each one counts); Words needing the same letter several times in a row, like "aaa"; Letters of a word that never appear in s.