Problem Breakdown
We are given a target string s and an array of query strings words. Our goal is to count how many individual strings in words appear as subsequences within s. A subsequence maintains relative character order but allows gaps between characters (e.g., “ace” from “abcde”).
Inputs:
s: String containing lowercase English letters. Length up to .words: List of strings, each length up to 50. Count up to 5000.
Outputs:
- Integer representing the count of matching words from the input list. Note that if a word appears multiple times in
words, it is counted separately for each occurrence (e.g., if “a” matches, and “a” appears twice inwords, we add 2 to total).
Edge Cases:
- Empty Words List: Loop simply won’t execute; returns 0.
- Missing Characters: If a character required by the word does not exist in
sat all (or after current position), that specific word fails immediately. - Duplicates: The problem asks for number of words[i], so we treat each entry independently rather than deduplicating unique strings first.
Intuition
A brute-force approach would iterate through every character of s to check if it matches the current target character in a word from start to finish. For one word, this takes . Doing this for all words results in time complexity roughly proportional to or simply if we scan s linearly each time.
Given constraints (), a naive scan could hit operations in the worst case (e.g., all words are “a…”). In Python, this risks Time Limit Exceeded (TLE).
Key Insight:
We can optimize character lookups by preprocessing s. Since we only care about lowercase English letters (‘a’-‘z’), we can store a list of indices for each character. For example, if ‘b’ appears at indices 2 and 5 in s, our map stores 'b': [2, 5].
When checking a word like “ba”, instead of scanning s linearly to find the first ‘a’, we can jump directly to index 0. Once matched, for the next character (say ‘c’), we use binary search (bisect) on our precomputed list to find the smallest occurrence after the current position in s. This reduces lookup from per word-character pair to .
Approach
- Preprocessing: Create a dictionary mapping each character present in
sto a sorted list of its indices (e.g., usingdefaultdict(list)). Iterate throughsonce (). - Processing Words: Initialize a counter for matches. Loop through every string in
words. - Matching Logic: For each word, maintain a variable tracking the current index within
s(initially -1 to indicate before start of string). Iterate through characters of the word:- Check if character exists in our map. If not, this word cannot be formed; break and skip counting it.
- Use binary search (
bisect_right) on the list of indices for that character to find the first occurrence strictly greater thancurrent_idx. - Update
current_idxto this new index.
- Counting: If we successfully iterate through all characters in a word without failing, increment our total count by 1 (for each instance).
Complexity Analysis
- Time Complexity: . Building the map takes linear time with respect to
s. Processing words involves iterating through characters of each word. For every character, we perform a binary search on lists up to size , taking logarithmic time relative to occurrences. Given constraints and alphabet size (26), this is highly efficient compared to naive scanning. - Space Complexity: to store the indices of characters in
s.
Solution
import bisect
from collections import defaultdict
def numMatchingSubseq(s: str, words: list[str]) -> int:
# Preprocess s into a map of character -> sorted list of indices
char_indices = defaultdict(list)
for idx, char in enumerate(s):
char_indices[char].append(idx)
count = 0
for word in words:
current_idx_in_s = -1
# Check each character in the word sequentially
possible_match = True
for char in word:
if not possible_match:
break
indices_list = char_indices.get(char)
# If character doesn't exist in s, or no valid index found after current_idx_in_s
if not indices_list:
possible_match = False
continue
# Find the smallest index strictly greater than current_idx_in_s
idx_pos = bisect.bisect_right(indices_list, current_idx_in_s)
# If all occurrences are <= current position (idx_pos == len), fail
if idx_pos >= len(indices_list):
possible_match = False
break
# Move pointer to the found index in s
current_idx_in_s = indices_list[idx_pos]
if possible_match:
count += 1
return count
# Example usage (not part of submission)
# print(numMatchingSubseq("abcde", ["a","bb","acd","ace"])) # Output: 3
Edge Cases Handled
- Character Not in
s: The map lookup returns an empty list or missing key; the code checks for this and marks the word as invalid immediately. - Subsequence Order Constraint: By using binary search to find indices strictly greater than the previous match (
bisect_right), we ensure relative order is preserved without re-scannings. - Duplicate Words in Input List: The loop iterates over every element of
words, so if “a” appears twice and matches, it increments count twice.