Problem Description

You are given a string s and an array of strings called words. Your task is to count how many strings in the words array are subsequences of the string s.

A subsequence is formed by deleting some (possibly zero) characters from the original string without changing the order of the remaining characters. For example, "ace" is a subsequence of "abcde" because you can delete 'b' and 'd' from "abcde" to get "ace", maintaining the relative order of 'a', 'c', and 'e'.

The solution uses a clever approach with queues organized by the first character of each word. It groups words by their current first character that needs to be matched. As we iterate through string s, when we encounter a character c, we check all words currently waiting for that character. If a word has only one character left (meaning we just matched its last character), we increment our answer. Otherwise, we remove the matched character from the word and place it in the queue corresponding to its new first character.

For example, if s = "abcde" and words = ["a", "bb", "acd", "ace"]:

• Initially, words are grouped: 'a' → ["a", "acd", "ace"], 'b' → ["bb"]
• When processing 'a' from s, we match it with all three words starting with 'a'
• "a" is complete (length 1), so answer increases by 1
• "acd" becomes "cd" and moves to queue 'c'
• "ace" becomes "ce" and also moves to queue 'c'
• The process continues through the string, tracking which words become complete subsequences

The final answer is the count of words that were successfully matched as subsequences.

Intuition

The naive approach would be to check each word individually against string s to see if it's a subsequence, which would require iterating through s multiple times. However, we can be more efficient by processing all words simultaneously in a single pass through s.

The key insight is that when we're checking if multiple words are subsequences of s, we're essentially tracking where each word is in its matching process. At any point, each word is waiting for a specific character (the next unmatched character in that word).

Think of it like multiple people reading the same book but looking for different sequences of letters. Instead of having each person read the entire book separately, we can have one person read the book aloud while everyone listens and marks when they hear the letter they're currently looking for.

This leads us to organize words by what character they're currently waiting for. We use a dictionary where each key is a character, and the value is a queue of words currently waiting for that character. When we encounter a character c in string s, we know exactly which words can make progress - those in the queue for character c.

For each word that matches the current character:

• If it was the last character needed (word length is 1), we've found a complete subsequence
• Otherwise, we remove the matched character and put the remaining part of the word into the queue for its new first character

This way, we only traverse string s once, and for each character, we only process the words that can actually make progress. The use of deques ensures efficient removal from the front and addition to the back of our waiting lists.

The beauty of this approach is that it transforms a problem that seems to require multiple string traversals into a single-pass algorithm with efficient bookkeeping.

Learn more about Trie, Binary Search, Dynamic Programming and Sorting patterns.

Solution Approach

The implementation uses a dictionary of deques to efficiently track and process words waiting for specific characters.

Data Structure Setup:

• Create a defaultdict(deque) called d where each key represents a character and each value is a deque containing words currently waiting for that character
• Initialize by iterating through all words and placing each word in the deque corresponding to its first character: d[w[0]].append(w)

Main Processing Loop: Iterate through each character c in string s:

1. Process all words waiting for character c:

   • Use for _ in range(len(d[c])) to process exactly the current number of words in the queue (important because we'll be modifying the queue)
   • For each word, remove it from the front of the queue: t = d[c].popleft()

2. Check if word is complete:

   • If len(t) == 1, this was the last character needed for this word
   • Increment the answer counter: ans += 1

3. Handle incomplete words:

   • If the word has more characters to match, remove the first character: t[1:]
   • Add the remaining portion to the queue for its new first character: d[t[1]].append(t[1:])

Example walkthrough with s = "abcde" and words = ["a", "bb", "acd"]:

Initial state: d = {'a': ["a", "acd"], 'b': ["bb"]}

• Process 'a':

  • "a" → length is 1, increment answer to 1
  • "acd" → becomes "cd", added to d['c']

• Process 'b':

  • "bb" → becomes "b", added to d['b']

• Process 'c':

  • "cd" → becomes "d", added to d['d']

• Process 'd':

  • "d" → length is 1, increment answer to 2

• Process 'e':

  • Nothing waiting for 'e'

Final answer: 2 (words "a" and "acd" are subsequences)

The algorithm's efficiency comes from only examining words that can make progress with the current character, avoiding redundant checks and achieving O(n + m) time complexity where n is the length of s and m is the total length of all words.

Example Walkthrough

Let's walk through the solution with s = "abcde" and words = ["ace", "aec", "bb"].

Step 1: Initialize the dictionary of deques We group words by their first character:

• d['a'] = ["ace", "aec"] (both start with 'a')
• d['b'] = ["bb"] (starts with 'b')

Step 2: Process each character in s = "abcde"

Processing 'a' (index 0):

• Check d['a']: has 2 words waiting
• Process "ace":
  • Remove from queue, length > 1
  • Remove first char → "ce"
  • Add to d['c']
• Process "aec":
  • Remove from queue, length > 1
  • Remove first char → "ec"
  • Add to d['e']
• State: d['c'] = ["ce"], d['e'] = ["ec"], d['b'] = ["bb"]

Processing 'b' (index 1):

• Check d['b']: has 1 word waiting
• Process "bb":
  • Remove from queue, length > 1
  • Remove first char → "b"
  • Add to d['b']
• State: d['c'] = ["ce"], d['e'] = ["ec"], d['b'] = ["b"]

Processing 'c' (index 2):

• Check d['c']: has 1 word waiting
• Process "ce":
  • Remove from queue, length > 1
  • Remove first char → "e"
  • Add to d['e']
• State: d['e'] = ["ec", "e"], d['b'] = ["b"]

Processing 'd' (index 3):

• Check d['d']: empty, nothing to process
• State unchanged

Processing 'e' (index 4):

• Check d['e']: has 2 words waiting
• Process "ec":
  • Remove from queue, length > 1
  • Remove first char → "c"
  • Add to d['c']
• Process "e":
  • Remove from queue, length = 1
  • Complete match! Increment answer to 1
• State: d['c'] = ["c"], d['b'] = ["b"]

Result:

• Answer = 1 (only "ace" is a subsequence of "abcde")
• "aec" is not a subsequence (needs 'e' before 'c')
• "bb" is not a subsequence (only one 'b' in s)

The algorithm efficiently tracks each word's progress through the string in a single pass, only processing words that can advance with the current character.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n + m * l)

• n is the length of string s
• m is the total number of words in the words list
• l is the average length of words

The algorithm iterates through each character in string s once (O(n)). For each character, it processes all words waiting for that character. In the worst case, each word gets processed character by character, and each character operation (slicing t[1:], appending to deque) takes O(l) time. Since each word is processed at most once for each of its characters, the total work done for all words is O(m * l). Therefore, the overall time complexity is O(n + m * l).

Space Complexity: O(m * l)

• The defaultdict d stores all words distributed across different character keys
• In the worst case, all m words are stored in the dictionary
• Each word takes O(l) space on average
• The slicing operation t[1:] creates new strings, but at any point, the total space used for all word fragments doesn't exceed O(m * l) since we're just storing progressively smaller suffixes of the original words

The space complexity is dominated by storing all the words (or their suffixes) in the dictionary structure, resulting in O(m * l) space complexity.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Modifying Queue While Iterating

One of the most common mistakes is directly iterating over the deque while modifying it:

Incorrect approach:

# This will cause issues!
for word in waiting_dict[char]:
    current_word = waiting_dict[char].popleft()
    # ... rest of logic

This creates problems because:

• The iterator gets confused when the deque size changes during iteration
• You might skip words or process words multiple times
• Could lead to infinite loops if you're adding back to the same queue

Correct approach:

# Get the current size first
current_queue_size = len(waiting_dict[char])
for _ in range(current_queue_size):
    current_word = waiting_dict[char].popleft()
    # ... rest of logic

2. String Slicing Inefficiency

Using string slicing current_word[1:] creates a new string object each time, which can be inefficient for long words:

Alternative approach using indices:

from collections import defaultdict, deque

class Solution:
    def numMatchingSubseq(self, s: str, words: List[str]) -> int:
        # Store tuples of (word, current_index)
        waiting_dict = defaultdict(deque)
      
        for word in words:
            waiting_dict[word[0]].append((word, 0))
      
        matching_count = 0
      
        for char in s:
            current_queue_size = len(waiting_dict[char])
            for _ in range(current_queue_size):
                word, idx = waiting_dict[char].popleft()
                idx += 1  # Move to next character
              
                if idx == len(word):
                    matching_count += 1
                else:
                    next_char = word[idx]
                    waiting_dict[next_char].append((word, idx))
      
        return matching_count

This approach avoids creating new string objects and instead tracks the current position in each word.

3. Not Handling Empty Strings

If the words array contains empty strings, the code will fail:

Problem:

waiting_dict[word[0]].append(word)  # IndexError if word is empty

Solution:

for word in words:
    if word:  # Check for non-empty string
        waiting_dict[word[0]].append(word)
    else:
        # Empty string is always a subsequence
        matching_count += 1

4. Using Regular Dictionary Instead of defaultdict

Using a regular dictionary requires checking if keys exist before accessing:

Inefficient approach:

waiting_dict = {}
for word in words:
    if word[0] not in waiting_dict:
        waiting_dict[word[0]] = deque()
    waiting_dict[word[0]].append(word)

The defaultdict(deque) automatically creates an empty deque for new keys, making the code cleaner and preventing KeyError exceptions.