792. Number of Matching Subsequences

Problem Description

The problem requires you to determine how many strings in the array words are subsequences of the string s. A subsequence of a string is defined as a sequence that can be derived from the original string by removing some characters without altering the order of the remaining characters. For instance, "ace" is a subsequence of "abcde" because you can remove 'b' and 'd' to get "ace". Your goal is to return the count of strings in words that can be formed in this way from the string s.

Intuition

To solve this problem, the key idea is to track the progress of each word in the words array as we iterate through the string s. Instead of checking each word against the entire string s at once, which would be inefficient, we use a smarter approach. We create a dictionary that maps the first character of each word to a queue holding tuples that represent the words. Each tuple consists of an index i and a position j, where i is the index of the word in the words array, and j is the position up to which we have successfully matched the word in words[i] with characters in s.

As we iterate through the string s, we get the queue of words (tuples) that are expecting the current character. For each word in the queue, if we find a matching character in s, we move to the next character in the word by incrementing j. If we reach the end of a word, it means we have successfully found it as a subsequence in s, and we increment our answer count (ans).

We use a queue because it efficiently supports removing elements from the front, allowing us to process the words in the order they are expecting to match characters from s. By organizing the words based on the next expected character, we only consider the relevant part of words for each character in s, making the process efficient.

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

Solution Approach

The solution approach makes use of the following algorithms, data structures, and patterns:

• Dictionary with Queue: A defaultdict(deque) from Python's collections module is used to map the first character of each word in words to a queue containing tuples of the form (i, j). Here i is the index of the word in the array words, and j is the current character position we have matched in the word so far.

• Character Iteration and Matching: The solution iterates through each character c in the string s and uses it to reference the queue of tuples waiting for that character (d[c]).

• Queue Processing: Within this iteration, another loop runs for the length of the queue d[c], which processes each tuple. For each tuple (i, j) dequeued from d[c], the j is incremented to point to the next character since the current one c is a match.

• Subsequence Completion Check: If the incremented j equals the length of the word words[i], it means all the characters in words[i] are matched in sequence with some characters of s, therefore words[i] is a subsequence of s. When this condition is met, the answer counter ans is incremented.

• Updating the Dictionary with Queues: If j is not equal to the length of the word, the tuple (i, j) is not completed yet and must wait for the next character words[i][j]. Hence, it is appended back into the queue corresponding to this next expected character d[words[i][j]].

In essence, the algorithm processes s character by character, moving 'pointers' through each word in words when a matching character is found, and recounts every time a word is completely matched as a subsequence.

The algorithm complexity is mainly O(N + M), where N is the length of the string s, and M is the total length of all words in words. It's because each character of each word is processed at most once when the corresponding character in s is found.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach in action. Consider the string s = "abcde" and the list of words words = ["a", "bb", "acd", "ace"]. We want to find how many words are subsequences of s.

To begin, we initialize our dictionary with queues, d, that will hold the progress for each word in words as we iterate over s. For our example, the initial state of the dictionary will be as follows since each queue will contain tuples with the index of the word in words and the initial character position 0.

1{
2  'a': deque([(0, 0), (2, 0), (3, 0)]),
3  'b': deque([(1, 0)]),
4}

Now we start iterating over s, character by character:

1. For the first character 'a' in s, we look in d to find the queue for 'a', which is deque([(0, 0), (2, 0), (3, 0)]). We have three words waiting to match the character 'a' in s.

   a. dequeue (0, 0): Since 'a' in s matches the first character of words[0] which is "a", it's a complete match. We increment ans to 1.

   b. dequeue (2, 0): Now we're looking at words[2] which is "acd". The character 'a' matched, so we increment j to 1 and requeue the tuple since "acd" is not yet fully matched. Now the tuple is (2, 1).

   c. dequeue (3, 0): Similarly, for words[3] which is "ace", we have a match on 'a', increment j to 1, and requeue the tuple to (3, 1).

   Now our dictionary looks like this:

   1{
   2  'b': deque([(1, 0)]),
   3  'c': deque([(2, 1), (3, 1)]),
   4}

2. The second character of s is 'b'. We check our dictionary for the queue under 'b', which is deque([(1, 0)]).

   a. dequeue (1, 0): We look at words[1] which is "bb". Since 'b' matches the first character, we increment j to 1 and enqueue the tuple (1, 1) back because it's still awaiting another 'b'.

   And the dictionary updates to:

   1{
   2  'c': deque([(2, 1), (3, 1)]),
   3  'b': deque([(1, 1)]),
   4}

3. Next, s gives us 'c'. We process the queue under 'c', which is deque([(2, 1), (3, 1)]).

   a. dequeue (2, 1): "acd" in words[2] has matched 'a' and now 'c', so j becomes 2. Since j is not equal to the length of "acd", we enqueue tuple (2, 2) since we are now waiting for 'd'.

   b. dequeue (3, 1): Similarly, "ace" in words[3] has matched 'a' and 'c', and j is incremented to 2, indicating we are waiting for 'e' next.

   Updated dictionary:

   1{
   2  'b': deque([(1, 1)]),
   3  'd': deque([(2, 2)]),
   4  'e': deque([(3, 2)]),
   5}

4. The next character in s is 'd', which affects the queue under 'd'.

   a. dequeue (2, 2): The tuple for "acd" is fully matched now because 'd' was the last needed character, so we increment ans by 1 (total ans is now 2).

   Dictionary after the operation:

   1{
   2  'b': deque([(1, 1)]),
   3  'e': deque([(3, 2)]),
   4}

5. The last character in s is 'e', and we process the queue under 'e'.

   a. dequeue (3, 2): Finally, "ace" is fully matched, and our total count ans is incremented by one more (total ans is now 3).

The end state of the dictionary is not relevant anymore since we have processed all of s. The algorithm finishes with ans = 3 because we've found that three out of four words in words are subsequences of s. The word "bb" was not a subsequence since the second 'b' couldn't be matched.

Solution Implementation

Time and Space Complexity

Time Complexity

The time complexity of the given code can be analyzed as follows:

• Initializing the dictionary d with a deque for each unique character has a space complexity that depends on the number of unique characters in words list, but initializing the deques themselves takes O(1) time.
• The first loop goes through all the words in words list to populate the dictionary d. Each word is processed in O(1) time to append its index and starting character position to the corresponding deque, resulting in O(n) time complexity for this step, where n is the number of words in words.
• The second loop goes through each character in the input string s. For each character c, it processes all indices (i, j) in d[c]. Since each word is exactly processed once, and each character in s results in at most one deque operation (either popleft or append), the number of operations is proportional to the length of s plus the total length of all words. Hence, the time complexity, in this case, is O(m + k), where m is the length of s and k is the sum of lengths of all words in words.

Thus, the overall time complexity combines the complexities of both loops, resulting in O(n + m + k).

Space Complexity

The space complexity of the code is determined by:

• The dictionary d which contains as many keys as there are unique starting characters in the words, and each key has a deque that contains at most n tuples (i, j), where n is the number of words. However, since each word can only be in one deque at a time, it's more precise to say that it contains a total of n tuples across all deques.
• There are no other data structures that require significant space.

Therefore, the space complexity is O(n), where n is the number of words in words.

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