Number of Matching Subsequences - Solution & Explanation
Problem Statement
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.
This implementation involves a helper function isSubsequence that checks if a given word is a subsequence of the string s. We iterate through each word in the array and utilize the helper function to accumulate the count of matching subsequences.
Complexity
Time Complexity: O(n * m), where n is the length of the string s and m is the average length of the words. Space Complexity: O(1) since it only uses constant extra space.
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.
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.
Complexity
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
Try this approach in the editor →Complexity Comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n * m), where n is the length of the string s and m is the average length of the words. Space Complexity: O(1) since it only uses constant extra space. |
| 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 | — |
Detailed 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 |
Video Solution
Number of Matching Subsequences Leetcode 792. || Intuition + Code + Example Walkthrough • Code with Alisha • 15,299 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Number of Matching Subsequences easy or hard?
How to solve Number of Matching Subsequences in O(n)?
What is the best approach for Number of Matching Subsequences?
What data structure is used in Number of Matching Subsequences?
What is the time complexity of Number of Matching Subsequences?
Number of Matching Subsequences Python or Java solution approach?
Is Number of Matching Subsequences asked at Google, Amazon, or Meta?
Ready to solve this problem?
Practice Number of Matching Subsequences with our built-in code editor and test cases.
Practice on FleetCode