# Number of Matching Subsequences
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/number-of-matching-subsequences)
Canonical: https://scaleengineer.com/dsa/problems/number-of-matching-subsequences
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Hash Table, String, Trie
**Companies:** [Visa](https://scaleengineer.com/companies/visa), [Salesforce](https://scaleengineer.com/companies/salesforce)
---
## Problem
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 * 104`
* `1 <= words.length <= 5000`
* `1 <= words[i].length <= 50`
* `s` and `words[i]` consist of only lowercase English letters.

# Approaches
## Brute-Force Subsequence Check
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.
**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.
**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.
### Explanation
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.

```java
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();
    }
}
```
### Algorithm
- Initialize a counter `count` to 0.
- For each `word` in the `words` array:
  - Call a helper function `isSubsequence(s, word)` to check if `word` is a subsequence of `s`.
  - The helper function uses a two-pointer approach. One pointer `i` for `s` and another `j` for `word`.
  - It iterates through `s` with `i`. If `s.charAt(i)` matches `word.charAt(j)`, it increments `j`.
  - If `j` reaches the end of `word`, it's a subsequence.
  - If the helper function returns true, increment `count`.
- Return `count`.

## Pre-computation of Character Indices with Binary Search
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.
**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.
**Pros:** Significantly faster than brute-force for a long string `s` and 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.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
- **Preprocessing:**
  - Create a map `charIndices` from characters to a list of their indices in `s`.
  - Iterate through `s` once to populate this map. The lists of indices will be naturally sorted.
- **Matching:**
  - Initialize `count = 0`.
  - For each `word` in `words`:
    - Initialize `lastIndex = -1` to track the last matched index in `s`.
    - For each character `c` in `word`:
      - Find the list of indices for `c` from `charIndices`.
      - 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 `lastIndex` to this new found index.
    - If all characters are found in order, increment `count`.
  - Return `count`.

## Optimized Single Pass with Waiting Pointers (Buckets)
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.
**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.
**Pros:** Highly efficient as it processes `s` only once.; Optimal time complexity for the given constraints.
**Cons:** Slightly more complex to conceptualize and implement due to the node/bucket data structure.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
- Create an array of lists called `waiting` of size 26. `waiting[i]` will store nodes representing words waiting for character `i + 'a'`.
- For each `word` in `words`, create a `Node` (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 `c` of string `s`:
  - Take the list of waiting nodes for character `c`. Let's call it `advancing`.
  - Clear the original waiting list for `c`.
  - For each `node` in `advancing`:
    - Advance the character pointer within the word (`node.index++`).
    - If the word is now fully matched (`node.index == word.length`), increment `count`.
    - Otherwise, place the updated `node` into the new waiting bucket corresponding to its next character.
- Return `count`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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 ans

```