Skip to main content
CodePeet

CodePeet 444 Complete DSA Sheet

Number of Matching Subsequences

Try it yourself
MediumProblemExternal link

Description

You get a string s and an array of strings words.

Return how many of the words are subsequences of s. A subsequence is what's left after deleting some letters (possibly none) without changing the order of the rest: "ace" is a subsequence of "abcde". Words can repeat, and every copy counts.

Examples

Example 1

Input: s = "abcde", words = ["a", "bb", "acd", "ace"]

Output: 3

Explanation: a, acd and ace can be made by deleting letters; bb needs two b's and s has one.

Example 2

Input: s = "dsahjpjauf", words = ["ahjpjau", "ja", "ahbwzgqnuk", "tnmlanowax"]

Output: 2

Explanation: ahjpjau and ja are subsequences; the other two have letters s doesn't.

Constraints

  • 1 ≤ s.length ≤ 5 × 10^4
  • 1 ≤ words.length ≤ 5000
  • 1 ≤ words[i].length ≤ 50
  • s and words[i] consist of only lowercase English letters.

Editorial

Brute Force

Intuition

Check each word on its own, the way Is Subsequence does: walk s from the start, and move to the word's next letter whenever s shows the one you're waiting for. If every letter of the word is matched, count it.

Step-by-Step Explanation

Let's check each word against s = "abcde":

  1. Walk s for "a". Its letters turn up in order at 0, so it's a subsequence. That's 1 so far.
  2. Walk s for "bb". Only 1 of its 2 letters turn up in order, so it isn't one. Still 1.
  3. Walk s for "acd". Its letters turn up in order at 0, 2, 3, so it's a subsequence. That's 2 so far.
  4. Walk s for "ace". Its letters turn up in order at 0, 2, 4, so it's a subsequence. That's 3 so far.

The answer is 3.

Walk s Once per Word — The row is s. Each step walks it for one word, marking where that word's letters were matched.

Algorithm

  1. For each word: walk s with a pointer into the word, advancing it on every match.
  2. If the pointer reaches the end of the word, count it.

Code

class Solution {
public:
    int numMatchingSubseq(string s, vector<string>& words) {
        int count = 0;
        for (const string& w : words) {
            size_t k = 0;
            for (size_t i = 0; i < s.size() && k < w.size(); i++)   // walk s, matching w's letters in order
                if (s[i] == w[k]) k++;
            if (k == w.size()) count++;
        }
        return count;
    }
};

class Solution:
    def numMatchingSubseq(self, s: str, words: list[str]) -> int:
        count = 0
        for w in words:
            k = 0
            for c in s:                         # walk s, matching w's letters in order
                if c == w[k]:
                    k += 1
                    if k == len(w):
                        break
            if k == len(w):
                count += 1
        return count

class Solution {
    public int numMatchingSubseq(String s, String[] words) {
        int count = 0;
        for (String w : words) {
            int k = 0;
            for (int i = 0; i < s.length() && k < w.length(); i++)   // walk s, matching w's letters in order
                if (s.charAt(i) == w.charAt(k)) k++;
            if (k == w.length()) count++;
        }
        return count;
    }
}

var numMatchingSubseq = function(s, words) {
    let count = 0;
    for (const w of words) {
        let k = 0;
        for (let i = 0; i < s.length && k < w.length; i++)   // walk s, matching w's letters in order
            if (s[i] === w[k]) k++;
        if (k === w.length) count++;
    }
    return count;
};

Complexity Analysis

Time Complexity: O(|words| · |s|)

A word that isn't a subsequence, or whose last letter comes late, walks all of s.

Space Complexity: O(1)

Why This Approach Is Not Efficient

5000 words times 5 × 10^4 letters is 2.5 × 10^8 steps (over the time limit in Python).

Every word walks s from the start again. Turn it around: walk s once, and at each letter, move forward exactly the words that were waiting for that letter.

Optimal Approach - Words Waiting on the Next Letter

Intuition

Keep 26 lists, one per letter. A word sits in the list of the next letter it needs. Walk s once: at each letter c, take the whole list for c out, and move each word in it one letter on. A word that has no letters left is a subsequence; any other word joins the list of its next letter.

Take the list out before refilling: a word like "bb" moves from the b list back into the b list, and it must wait for the next b of s, not use this one twice.

It's a hash table whose keys are letters and whose values are lists of words.

Step-by-Step Explanation

Let's walk s = "abcde" once:

  1. File every word under its first letter. The value word@m means m letters of it are matched.
  2. s gives a. "a" is complete; "acd" now waits for c; "ace" now waits for c. Done so far, 1.
  3. s gives b. "bb" now waits for b. Done so far, 1.
  4. s gives c. "acd" now waits for d; "ace" now waits for e. Done so far, 1.
  5. s gives d. "acd" is complete. Done so far, 2.
  6. s gives e. "ace" is complete. Done so far, 3.

The answer is 3.

Wake the Words Waiting on Each Letter — The row is s; the table lists the words waiting on each letter (word@m: m letters matched).

Algorithm

  1. Make 26 empty lists; put each word, with 0 letters matched, in the list of its first letter.
  2. For each letter c of s: take out the list for c. For each word in it: if this was its last letter, count it; otherwise put it in the list of its next letter.
  3. Return the count.

Code

class Solution {
public:
    int numMatchingSubseq(string s, vector<string>& words) {
        vector<vector<pair<int, int>>> waiting(26);          // next letter needed -> {word index, letters matched}
        for (int i = 0; i < (int)words.size(); i++) waiting[words[i][0] - 'a'].push_back({i, 0});
        int done = 0;
        for (char c : s) {
            vector<pair<int, int>> ready;
            swap(ready, waiting[c - 'a']);                   // take this letter's list before refilling it
            for (auto [i, m] : ready) {
                if (m + 1 == (int)words[i].size()) done++;   // the whole word is matched
                else waiting[words[i][m + 1] - 'a'].push_back({i, m + 1});
            }
        }
        return done;
    }
};

class Solution:
    def numMatchingSubseq(self, s: str, words: list[str]) -> int:
        waiting = [[] for _ in range(26)]       # next letter needed -> (word, letters matched so far)
        for w in words:
            waiting[ord(w[0]) - ord('a')].append((w, 0))
        done = 0
        for c in s:
            k = ord(c) - ord('a')
            ready, waiting[k] = waiting[k], []  # take this letter's list before refilling it
            for w, m in ready:
                if m + 1 == len(w):
                    done += 1                   # the whole word is matched
                else:
                    waiting[ord(w[m + 1]) - ord('a')].append((w, m + 1))
        return done

class Solution {
    public int numMatchingSubseq(String s, String[] words) {
        List<List<int[]>> waiting = new ArrayList<>();       // next letter needed -> {word index, letters matched}
        for (int k = 0; k < 26; k++) waiting.add(new ArrayList<>());
        for (int i = 0; i < words.length; i++) waiting.get(words[i].charAt(0) - 'a').add(new int[]{i, 0});
        int done = 0;
        for (char c : s.toCharArray()) {
            List<int[]> ready = waiting.get(c - 'a');
            waiting.set(c - 'a', new ArrayList<>());          // take this letter's list before refilling it
            for (int[] e : ready) {
                String w = words[e[0]];
                if (e[1] + 1 == w.length()) done++;          // the whole word is matched
                else waiting.get(w.charAt(e[1] + 1) - 'a').add(new int[]{e[0], e[1] + 1});
            }
        }
        return done;
    }
}

var numMatchingSubseq = function(s, words) {
    let waiting = Array.from({ length: 26 }, () => []);   // next letter needed -> [word, letters matched]
    for (const w of words) waiting[w.charCodeAt(0) - 97].push([w, 0]);
    let done = 0;
    for (const c of s) {
        const k = c.charCodeAt(0) - 97;
        const ready = waiting[k];
        waiting[k] = [];                        // take this letter's list before refilling it
        for (const [w, m] of ready) {
            if (m + 1 === w.length) done++;     // the whole word is matched
            else waiting[w.charCodeAt(m + 1) - 97].push([w, m + 1]);
        }
    }
    return done;
};

Complexity Analysis

Time Complexity: O(|s| + total length of the words)

Each letter of s is visited once, and each letter of each word moves its word once.

Space Complexity: O(|words|) for the lists

Common Mistakes

Each of these looks right on a quick read, and the tests still reject it. The outputs below come from running the code.

Refilling the list you're reading. ready = waiting[k] # and then appending to waiting[k] while walking ready

On s = "abcde", words = ["a", "bb", "acd", "ace"], it returns 4; the answer is 3. Walking waiting[c] while appending to it lets a word whose next letter is c again (the second b of "bb") move on with the same letter of s. Take the list out first, then refill it.

Counting each distinct word once. for w in set(words):

On s = "a", words = ["a", "a", "a"], it returns 1; the answer is 3. Words can repeat, and every copy counts. Turning the list into a set first throws the copies away.

Checking the letters, not the order. all(c in set(s) for c in w)

On s = "abc", words = ["cb", "ba", "ca", "abc"], it returns 4; the answer is 1. A subsequence keeps the order: "cb" isn't a subsequence of "abc" even though both letters are there.

Where This Pattern Is Taught

This problem practises a hash table of waiting lists, keyed by what each item needs next. It's taught in Frequency Counting with Hash Maps.