Number of Matching Subsequences
MedPrompt
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.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach iterates through each word in the words array and, for each word, checks if it is a subsequence of the string s. This is the most straightforward but least efficient method, serving as a baseline.
Algorithm
- Initialize a counter
countto 0. - For each
wordin thewordsarray:- Call a helper function
isSubsequence(s, word)to check ifwordis a subsequence ofs. - The helper function uses a two-pointer approach. One pointer
iforsand anotherjforword. - It iterates through
swithi. Ifs.charAt(i)matchesword.charAt(j), it incrementsj. - If
jreaches the end ofword, it's a subsequence. - If the helper function returns true, increment
count.
- Call a helper function
- Return
count.
Walkthrough
The core of this method is a helper function, isSubsequence(s, word), which determines if word is a subsequence of s. This function uses a two-pointer technique. One pointer traverses s, and the other traverses word. The pointer for word only advances when a matching character is found in s. If the word pointer reaches the end of the word, it means all its characters were found in s in the correct relative order, confirming it's a subsequence. The main function calls this helper for every word and counts the successes.
class Solution { public int numMatchingSubseq(String s, String[] words) { int count = 0; for (String word : words) { if (isSubsequence(s, word)) { count++; } } return count; } private boolean isSubsequence(String s, String word) { int i = 0; // pointer for s int j = 0; // pointer for word while (i < s.length() && j < word.length()) { if (s.charAt(i) == word.charAt(j)) { j++; } i++; } return j == word.length(); }}Complexity
Time
O(W * N), where `W` is the number of words and `N` is the length of `s`. For each of the `W` words, we might scan the entire string `s` in the worst case.
Space
O(1), as we only use a few variables for pointers, not counting the input storage.
Trade-offs
Pros
Simple to understand and implement.
Requires minimal extra memory.
Cons
Highly inefficient for the given constraints as it repeatedly scans the long string
s.Very likely to result in a "Time Limit Exceeded" (TLE) error on competitive programming platforms.
This approach improves upon the brute-force method by pre-processing the string s to avoid repeated linear scans. We store the indices of each character of s in a map. Then, for each word, we can efficiently find the required characters in order using binary search on these index lists.
Algorithm
- Preprocessing:
- Create a map
charIndicesfrom characters to a list of their indices ins. - Iterate through
sonce to populate this map. The lists of indices will be naturally sorted.
- Create a map
- Matching:
- Initialize
count = 0. - For each
wordinwords:- Initialize
lastIndex = -1to track the last matched index ins. - For each character
cinword:- Find the list of indices for
cfromcharIndices. - If the list doesn't exist, the word cannot be a subsequence.
- Binary search in the list for the smallest index strictly greater than
lastIndex. - If no such index exists, the word is not a subsequence.
- Otherwise, update
lastIndexto this new found index.
- Find the list of indices for
- If all characters are found in order, increment
count.
- Initialize
- Return
count.
- Initialize
Walkthrough
First, we create a map where keys are characters ('a' through 'z') and values are sorted lists of indices where that character appears in s. This takes a single pass through s.
Then, for each word, we check for the subsequence property. We keep track of the last matched index in s, let's call it lastIndex. For each character c in the word, we look up its index list in our map. We then perform a binary search on this list to find the first index that is strictly greater than lastIndex. If we find such an index, we update lastIndex and continue to the next character. If we cannot find such an index for any character, the word is not a subsequence. If we successfully process all characters of the word, we count it as a match.
import java.util.*; class Solution { public int numMatchingSubseq(String s, String[] words) { Map<Character, List<Integer>> charIndices = new HashMap<>(); for (int i = 0; i < s.length(); i++) { char c = s.charAt(i); charIndices.computeIfAbsent(c, k -> new ArrayList<>()).add(i); } int count = 0; for (String word : words) { if (isSubsequence(word, charIndices)) { count++; } } return count; } private boolean isSubsequence(String word, Map<Character, List<Integer>> charIndices) { int lastIndex = -1; for (char c : word.toCharArray()) { List<Integer> indices = charIndices.get(c); if (indices == null) { return false; // Character not in s } // Binary search for the smallest index > lastIndex int searchResult = Collections.binarySearch(indices, lastIndex + 1); if (searchResult < 0) { // If not found, insertion point is -(insertion point) - 1 int insertionPoint = -searchResult - 1; if (insertionPoint == indices.size()) { return false; // No valid index found } lastIndex = indices.get(insertionPoint); } else { // Found an exact match for lastIndex + 1 lastIndex = indices.get(searchResult); } } return true; }}Complexity
Time
O(N + W * L * log(N)), where `N` is `s.length()`, `W` is `words.length`, and `L` is the max length of a word. O(N) for preprocessing. For each of the `W` words of max length `L`, we do `L` binary searches on lists of size up to `N`.
Space
O(N), where N is the length of `s`. In the worst case (if all characters in `s` are distinct), we store `N` indices in total across all lists in the map.
Trade-offs
Pros
Significantly faster than brute-force for a long string
sand many words.The pre-computation step is done only once.
Cons
Requires extra space to store the character indices, which can be proportional to the length of
s.The implementation is more complex than the brute-force approach.
This is the most efficient approach, which processes the string s only once. Instead of checking each word against s individually, we iterate through s and advance all words that are waiting for the current character simultaneously. This is achieved by grouping words into 'buckets' based on the character they are currently waiting for.
Algorithm
- Create an array of lists called
waitingof size 26.waiting[i]will store nodes representing words waiting for characteri + 'a'. - For each
wordinwords, create aNode(containing the word and current index 0) and add it to the bucket corresponding to its first character. - Initialize
count = 0. - Iterate through each character
cof strings:- Take the list of waiting nodes for character
c. Let's call itadvancing. - Clear the original waiting list for
c. - For each
nodeinadvancing:- Advance the character pointer within the word (
node.index++). - If the word is now fully matched (
node.index == word.length), incrementcount. - Otherwise, place the updated
nodeinto the new waiting bucket corresponding to its next character.
- Advance the character pointer within the word (
- Take the list of waiting nodes for character
- Return
count.
Walkthrough
We use an array of lists (or "buckets"), one for each character 'a' through 'z'. Each bucket waiting[c] stores nodes representing words that are waiting for character c to appear in s. A node can be a simple object containing the word and the index of the character we are currently looking for.
Initially, we go through all words and place them into the bucket corresponding to their first character. Then, we iterate through s. For each character c in s, we process all the word nodes in waiting[c]. For each processed node, we advance its character index. If the word is now complete, we increment our result counter. If not, we move the node to the new bucket corresponding to its next character.
import java.util.*; class Solution { // A node to store the word and the current index to be matched class Node { String word; int index; Node(String word, int index) { this.word = word; this.index = index; } } public int numMatchingSubseq(String s, String[] words) { // Buckets for each character 'a' through 'z' List<Node>[] waiting = new ArrayList[26]; for (int i = 0; i < 26; i++) { waiting[i] = new ArrayList<>(); } // Place all words into buckets based on their first character for (String word : words) { waiting[word.charAt(0) - 'a'].add(new Node(word, 0)); } int count = 0; // Iterate through the main string s for (char c : s.toCharArray()) { int charIndex = c - 'a'; List<Node> advancing = waiting[charIndex]; waiting[charIndex] = new ArrayList<>(); // Clear the current bucket for (Node node : advancing) { node.index++; // Advance the pointer in the word if (node.index == node.word.length()) { // Reached the end of the word, it's a subsequence count++; } else { // Move to the bucket for the next character char nextChar = node.word.charAt(node.index); waiting[nextChar - 'a'].add(node); } } } return count; }}Complexity
Time
O(N + L), where `N` is the length of `s` and `L` is the sum of the lengths of all words in `words`. We iterate through `s` once (O(N)), and each character of each word is processed exactly once (O(L)).
Space
O(W), where `W` is the number of words. In the worst case, all `W` words could be waiting in the same bucket at the same time.
Trade-offs
Pros
Highly efficient as it processes
sonly once.Optimal time complexity for the given constraints.
Cons
Slightly more complex to conceptualize and implement due to the node/bucket data structure.
Solutions
Solution
class Solution {public int numMatchingSubseq(String s, String[] words) { Deque<int[]>[] d = new Deque[26]; Arrays.setAll(d, k->new ArrayDeque<>()); for (int i = 0; i < words.length; ++i) { d[words[i].charAt(0) - 'a'].offer(new int[]{i, 0}); } int ans = 0; for (char c : s.toCharArray()) { var q = d[c - 'a']; for (int t = q.size(); t > 0; --t) { var p = q.pollFirst(); int i = p[0], j = p[1] + 1; if (j == words[i].length()) { ++ans; } else { d[words[i].charAt(j) - 'a'].offer(new int[]{i, j}); } } } return ans; }}class Solution {public: int numMatchingSubseq(string s, vector<string> &words) { vector<queue<pair<int, int>>> d(26); for (int i = 0; i < words.size(); ++i) d[words[i][0] - 'a'].emplace(i, 0); int ans = 0; for (char &c : s) { auto &q = d[c - 'a']; for (int t = q.size(); t; --t) { auto [i, j] = q.front(); q.pop(); if (++j == words[i].size()) ++ans; else d[words[i][j] - 'a'].emplace(i, j); } } return ans; }};class Solution: def numMatchingSubseq(self, s: str, words: List[str]) -> int: d = defaultdict(deque) for i, w in enumerate(words): d[w[0]]. append((i, 0)) ans = 0 for c in s: for _ in range(len(d[c])): i, j = d[c]. popleft() j += 1 if j == len(words[i]): ans += 1 else: d[words[i][j]]. append((i, j)) return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.