Number of Matching Subsequences - Video Solutions
Number of Matching Subsequences Leetcode 792. || Intuition + Code + Example Walkthrough
Number of Matching Subsequences - Video Solution
Watch 10 video solutions for Number of Matching Subsequences, a medium level problem involving Array, Hash Table, String. This walkthrough by Code with Alisha has 15,299 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
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 |