Number of Matching Subsequences — Problem & Solution
Number of Matching Subsequences solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Number of Matching Subsequences is a medium coding problem on strings, binary search and two pointers, asked in Amazon, Google and Meta interviews.
- Difficulty: Medium
- Topics: Strings, Binary Search, Two Pointers
- Asked at: Amazon, Google, Meta
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given a string s and an array of strings words, return how many entries of words are subsequences of s.
A subsequence is formed by deleting zero or more characters without reordering the rest. Duplicates in words are counted separately.
Example 1
Input: s = "codekairo", words = ["code","kai","ckr","xyz"]
Output: 3
Explanation: "code", "kai" and "ckr" can all be read left to right inside s; "xyz" cannot.
Example 2
Input: s = "abcde", words = ["a","bb","acd","ace"]
Output: 3
Example 3
Input: s = "dsahjpjauf", words = ["ahjpjau","ja","ahbwzgqnuk","tnmlanowax"]
Output: 2
Constraints
1 <= s.length <= 500001 <= words.length <= 50001 <= words[i].length <= 50All strings consist of lowercase English letters.
Hints for Number of Matching Subsequences
Hint 1
Testing one word is a simple two-pointer walk: advance through
s, ticking off the word's characters in order.Hint 2
Doing that per word is O(|s| · |words|), which is the straightforward answer and fine at these limits.
Hint 3
The faster route buckets the words by their next needed character and sweeps
sonce, moving each waiting word forward as its character arrives.
How to solve Number of Matching Subsequences
A word is a subsequence when a greedy left-to-right match consumes all of it: always take the earliest possible occurrence of the next needed character.
Approach
- For each word, set a pointer
iat its start. - Walk
sonce; whenever the current character ofsequalsword[i], advancei. - The word matches if
ireaches the end of the word. - Count the matching words.
Why it works
The greedy match is optimal: if any embedding exists, taking the earliest occurrence of each character leaves at least as much of s available for the rest, so the greedy walk succeeds whenever some embedding does.
Complexity
- Time —
O(|s| · |words|) for the direct method; O(|s| + total word length) with the bucketing trick - Space —
O(1) for the direct method
Pitfalls
- Checking
s.includes(word)tests for a substring, which is a different (stricter) relation. - Restarting the scan of
sfor each character of the word is quadratic per word.
Reference solution
Python
from typing import List
def numMatchingSubseq(s: str, words: List[str]) -> int:
def is_sub(w: str) -> bool:
i = 0
for c in s:
if i < len(w) and c == w[i]:
i += 1
return i == len(w)
return sum(1 for w in words if is_sub(w))Java
public static int numMatchingSubseq(String s, String[] words) {
int total = 0;
for (String w : words) {
int i = 0;
for (int j = 0; j < s.length() && i < w.length(); j++) {
if (s.charAt(j) == w.charAt(i)) i++;
}
if (i == w.length()) total++;
}
return total;
}C++
int numMatchingSubseq(string s, vector<string>& words) {
int total = 0;
for (const string& w : words) {
size_t i = 0;
for (size_t j = 0; j < s.size() && i < w.size(); j++) {
if (s[j] == w[i]) i++;
}
if (i == w.size()) total++;
}
return total;
}JavaScript
var numMatchingSubseq = function(s, words) {
var isSub = function(w) {
var i = 0;
for (var j = 0; j < s.length && i < w.length; j++) {
if (s.charAt(j) === w.charAt(i)) i++;
}
return i === w.length;
};
var total = 0;
for (var t = 0; t < words.length; t++) {
if (isSub(words[t])) total++;
}
return total;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Binary Search