Number of Matching Subsequences solution and explanation
Google
9 more videos on this problem
Number of Matching Subsequences Leetcode 792. || Intuition + Code + Example WalkthroughCode with Alisha · 13:59 · 15K views
Number of Matching Subsequences | Leetcode 792 | Live coding sessionCoding Decoded · 9:26 · 11K views
LeetCode 792. Number of Matching SubsequencesHappy Coding · 23:16 · 6K views
Leetcode - Number of Matching Subsequences (Python)Timothy H Chang · 8:25 · 4K views
Daily Leetcode #841: Jul 20, 2022 - 792. Number of Matching SubsequencesProgramming Live with Larry · 12:55 · 1K views
Number of Matching Subsequences | LeetCode 792 | Coders CampCoders Camp · 11:02 · 1K views
Number of Matching Subsequences | Leetcode #792 | String | Arrays | JavaCode Junction · 11:46 · 764 views
792. Number of Matching Subsequences | English | MediumSimple Code - 단순코드 · 11:51 · 706 views
Coding Interview Problem - Number of Matching SubsequencesKnapsack · 7:07 · 592 views
Number of Matching Subsequences | C++ | LeetCode Solution 792Gantavya Malviya · 19:35 · 159 views
The problem
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".
Example 1:
Input: s = "abcde", words = ["a","bb","acd","ace"] Output: 3 Explanation: There are three strings in words that are a subsequence of s: "a", "acd", "ace".
Example 2:
Input: s = "dsahjpjauf", words = ["ahjpjau","ja","ahbwzgqnuk","tnmlanowax"] Output: 2
Constraints:
1 <= s.length <= 5 * 1041 <= words.length <= 50001 <= words[i].length <= 50sandwords[i]consist of only lowercase English letters.
Approach overview
Problem Overview: You are given a string s and an array of words. The task is to count how many of those words are subsequences of s. A word is a subsequence if its characters appear in the same order inside s, though not necessarily contiguously.
Approach 1: Brute Force Subsequence Check (Time: O(W * |s|), Space: O(1))
The straightforward approach checks every word individually against the main string. For each word, run a two-pointer scan: one pointer moves through s, the other through the word. When characters match, advance both pointers; otherwise only move the pointer in s. If the word pointer reaches the end, the word is a valid subsequence. This solution uses simple iteration over a string and requires no additional data structures. The downside is repeated scans of s for every word, which becomes expensive when the word list is large.
Approach 2: Efficient Group Matching Using Buckets (Time: O(|s| + total characters in words), Space: O(W))
A more scalable strategy processes all words simultaneously. Create 26 buckets (or a hash table) where each bucket stores iterators of words waiting for a specific character. Initially, place every word in the bucket corresponding to its first character. Then iterate through s. For each character c, take the list of words waiting for c, advance their pointer to the next character, and move them to the bucket of the next required character. If advancing reaches the end of the word, you found a valid subsequence. Each character of each word moves between buckets only once, which keeps the overall work proportional to the total length of all words.
This bucket technique behaves like a streaming matcher. Instead of scanning s repeatedly, the algorithm processes it once and lets words "react" when their needed character appears. The idea is similar to grouping tasks in an array of queues where each queue represents the next required character. This reduces redundant work and handles large input efficiently.
Recommended for interviews: Interviewers typically expect the bucket-based grouping approach. The brute force solution shows you understand how subsequences work, but it does not scale when thousands of words must be checked. The bucket strategy demonstrates stronger algorithmic thinking because it transforms repeated scans into a single pass over s while incrementally advancing every candidate word.
Approach 1: Brute Force Approach
Brute Force Approach: In this approach, for each word in the words array, we will check whether it is a subsequence of the string s or not. This is achieved by iterating over the characters of the word and trying to match them sequentially in the string s.
def is_subsequence(s, word):
it = iter(s)
return all(char in it for char in word)
class Solution:
def numMatchingSubseq(self, s: str, words: List[str]) -> int:
count = 0
for word in words:
if is_subsequence(s, word):
count += 1
return countpublic class Solution {
public boolean isSubsequence(String s, String word) {
int i = 0, j = 0;
while (i < s.length() && j < word.length()) {
if (s.charAt(i) == word.charAt(j)) {
j++;
}
i++;
}
return j == word.length();
}
public int numMatchingSubseq(String s, String[] words) {
int count = 0;
for (String word : words) {
if (isSubsequence(s, word)) {
count++;
}
}
return count;
}
}#include <vector>
#include <string>
bool isSubsequence(const std::string& s, const std::string& word) {
int i = 0, j = 0;
while (i < s.size() && j < word.size()) {
if (s[i] == word[j]) {
j++;
}
i++;
}
return j == word.size();
}
int numMatchingSubseq(const std::string& s, const std::vector<std::string>& words) {
int count = 0;
for (const auto& word : words) {
if (isSubsequence(s, word)) {
count++;
}
}
return count;
}function isSubsequence(s, word) {
let i = 0, j = 0;
while (i < s.length && j < word.length) {
if (s[i] === word[j]) {
j++;
}
i++;
}
return j === word.length;
}
function numMatchingSubseq(s, words) {
let count = 0;
for (const word of words) {
if (isSubsequence(s, word)) {
count++;
}
}
return count;
}#include <stdbool.h>
#include <string.h>
bool isSubsequence(char* s, char* word) {
int i = 0, j = 0;
while (i < strlen(s) && j < strlen(word)) {
if (s[i] == word[j]) {
j++;
}
i++;
}
return j == strlen(word);
}
int numMatchingSubseq(char* s, char** words, int wordsSize) {
int count = 0;
for (int i = 0; i < wordsSize; i++) {
if (isSubsequence(s, words[i])) {
count++;
}
}
return count;
}public class Solution {
public bool IsSubsequence(string s, string word) {
int i = 0, j = 0;
while (i < s.Length && j < word.Length) {
if (s[i] == word[j]) {
j++;
}
i++;
}
return j == word.Length;
}
public int NumMatchingSubseq(string s, string[] words) {
int count = 0;
foreach (var word in words) {
if (IsSubsequence(s, word)) {
count++;
}
}
return count;
}
}In the Python implementation, a helper function is_subsequence uses an iterator to determine if the word is a subsequence of the string s. This method leverages Python's expressive iteration features for a concise result.
Time Complexity: O(n * m). Space Complexity: O(1).
Approach 2: Efficient Group Matching Using Buckets
Efficient Group Matching: Group words by their initial characters in a dictionary and iterate over the string s to manage these groups of words, repositioning them towards completion as their current character is matched. This avoids re-checking each word from the beginning every time.
from collections import defaultdict
def numMatchingSubseq(s, words):
waiting = defaultdict(list)
for word in words:
waiting[word[0]].append(iter(word[1:]))
for char in s:
for it in waiting.pop(char, []):
next_char = next(it, None)
if next_char:
waiting[next_char].append(it)
return len(waiting[''])import java.util.*;
public class Solution {
public int numMatchingSubseq(String s, String[] words) {
Map<Character, Queue<Iterator<Character>>> waiting = new HashMap<>();
for (char c = 'a'; c <= 'z'; c++) waiting.put(c, new LinkedList<>());
for (String word : words)
waiting.get(word.charAt(0)).add(word.chars().mapToObj(c -> (char) c).iterator());
for (char c : s.toCharArray()) {
Queue<Iterator<Character>> queue = waiting.get(c);
for (int i = queue.size(); i > 0; i--) {
Iterator<Character> it = queue.poll();
if (!it.hasNext())
waiting.get('').add(it);
else
waiting.get(it.next()).add(it);
}
}
return waiting.get('').size();
}
}In this Python approach, we store word iterators in a dictionary waiting, initially keyed by their starting character. As we advance through s, we update the waiting list for each character to track partially matched words, dramatically improving efficiency.
Time Complexity: O(n + m), where n is the length of s and m is the total number of characters across all words. Space Complexity: O(m) due to storage of iterators.
Approach 3: Default Approach
func numMatchingSubseq(s string, words []string) (ans int) {
d := [26][]string{}
for _, w := range words {
d[w[0]-'a'] = append(d[w[0]-'a'], w)
}
for _, c := range s {
q := d[c-'a']
d[c-'a'] = nil
for _, t := range q {
if len(t) == 1 {
ans++
} else {
d[t[1]-'a'] = append(d[t[1]-'a'], t[1:])
}
}
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n * m). Space Complexity: O(1). |
| Efficient Group Matching Using Buckets | Time Complexity: O(n + m), where n is the length of s and m is the total number of characters across all words. Space Complexity: O(m) due to storage of iterators. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Subsequence Check | O(W * |s|) | O(1) | Small input sizes or quick baseline implementation |
| Efficient Group Matching Using Buckets | O(|s| + total characters in words) | O(W) | Large word lists where repeated scans of the main string would be expensive |
Frequently asked questions
Is Number of Matching Subsequences easy or hard?
Number of Matching Subsequences is rated Medium on LeetCode. The brute force subsequence check is straightforward, but achieving optimal performance requires recognizing the bucket grouping technique that processes all words simultaneously.
How to solve Number of Matching Subsequences in O(n)?
Use a bucket system that groups words by the next character they expect. Initialize buckets using the first character of each word. While scanning the main string, advance all words waiting for the current character and place them in the bucket of their next required character. This avoids repeated scans and processes the string in a single pass.
What is the best approach for Number of Matching Subsequences?
The most efficient approach uses bucket-based grouping of words by the next character they are waiting for. As you iterate through the main string, you advance all words waiting for that character and move them to the next bucket. This processes each character of every word only once, giving O(|s| + total characters in words) time complexity.
What data structure is used in Number of Matching Subsequences?
The optimal solution uses an array or hash map of buckets where each bucket stores iterators or pointers into words waiting for a specific character. Queues or lists are typically used inside each bucket to track progress through each word.
What is the time complexity of Number of Matching Subsequences?
The optimal bucket-based solution runs in O(|s| + total characters across all words). Each character in the main string is processed once, and each character in every word moves between buckets at most once. The brute force method takes O(W * |s|) time because it scans the main string separately for each word.
Number of Matching Subsequences Python or Java solution approach?
Both Python and Java implementations typically use an array of 26 lists (or queues). Each list stores pairs representing a word and the current index being matched. As the algorithm scans the main string, it advances each word's index and moves it to the next bucket until the word is fully matched.
Is Number of Matching Subsequences asked at Google, Amazon, or Meta?
Number of Matching Subsequences appears in interview preparation lists for companies such as Amazon, Google, and Meta. The problem tests knowledge of subsequences, efficient string processing, and grouping techniques using hash maps or arrays.