Number of Matching Subsequences

Medium Arrays & Hashing Hashing Original on LeetCode

Number of Matching Subsequences is a medium arrays & hashing problem solved with the hashing pattern. The best approach, optimal (buckets of waiting words), runs in O(|s| + T) time and O(W) space. Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force (two pointers per word) up.

Problem

You are given a string s and an array of strings words. Count how many of the words are subsequences of s.

A word is a subsequence of s if you can obtain it by deleting zero or more characters from s without changing the order of the characters that remain. For example, "pat" is a subsequence of "planet", but "tan" is not. Every entry of words is counted on its own, even if the same word appears several times.

Examples

Example 1

Input
s = "planet", words = ["pat", "lane", "net", "ten", "p"]
Output
4
Why
"pat", "lane", "net" and "p" can be read from s left to right; "ten" cannot, because the only 'e' in s comes before the 't'.

Example 2

Input
s = "xyz", words = ["xz", "zy", "xyz", "xyzz"]
Output
2
Why
"xz" and "xyz" match. "zy" has the letters in the wrong order and "xyzz" needs two z's.

Example 3

Input
s = "aab", words = ["ab", "ab", "ba"]
Output
2
Why
Each copy of a repeated word is counted separately, so "ab" counts twice.

Constraints

  • 1 <= s.length <= 5 * 10^4
  • 1 <= words.length <= 5000
  • 1 <= words[i].length <= 50
  • s and every words[i] consist of lowercase English letters.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 10 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (two pointers per word)O(W · (|s| + L))O(1)
Better (positions per letter + binary search)O(|s| + T · log |s|)O(|s|)
Optimal (buckets of waiting words)O(|s| + T)O(W)

1Brute force (two pointers per word)

TimeO(W · (|s| + L))Every one of the W words may scan the whole of s (and its own L letters).
SpaceO(1)Only two pointers and a counter.

Check each word on its own: walk through s with one pointer and through the word with another, advancing the word pointer whenever the characters match. The word is a subsequence if its pointer reaches the end.

  1. count = 0.
  2. For each word: j = 0; for each character of s, if j < word.length and it equals word[j], j++.
  3. If j == word.length, count++.
class Solution {
    public int numMatchingSubseq(String s, String[] words) {
        int count = 0;
        for (String w : words) {
            int j = 0;
            for (int i = 0; i < s.length() && j < w.length(); i++) {
                if (s.charAt(i) == w.charAt(j)) j++;
            }
            if (j == w.length()) count++;
        }
        return count;
    }
}

3Optimal (buckets of waiting words)

TimeO(|s| + T)The scan over s is linear, and each letter of each word causes exactly one move between buckets, so T letters in total cost O(T).
SpaceO(W)Every word sits in exactly one bucket at a time.

Scan s exactly once and move all words forward together. Each word is represented by (word index, position of the next letter it needs), and it waits in the bucket of that letter. When the scan reads letter c, empty bucket c: every word in it advances by one; a word that has used all its letters is counted, the others move to the bucket of their next needed letter. A word that needs c again goes into the fresh bucket c and waits for a later c.

  1. buckets = 26 empty lists; put (i, 0) into the bucket of words[i][0] for every word.
  2. For each character c of s: take the list in bucket c and replace it with an empty list.
  3. For each (i, p) in the taken list: p++; if p == words[i].length, count++; else add (i, p) to the bucket of words[i][p].
  4. Return count.
class Solution {
    public int numMatchingSubseq(String s, String[] words) {
        List<List<int[]>> buckets = new ArrayList<>();
        for (int c = 0; c < 26; c++) buckets.add(new ArrayList<>());
        for (int i = 0; i < words.length; i++) {
            buckets.get(words[i].charAt(0) - 'a').add(new int[] { i, 0 });
        }

        int count = 0;
        for (int k = 0; k < s.length(); k++) {
            int c = s.charAt(k) - 'a';
            List<int[]> waiting = buckets.get(c);
            buckets.set(c, new ArrayList<>());
            for (int[] item : waiting) {
                String w = words[item[0]];
                int p = item[1] + 1;
                if (p == w.length()) {
                    count++;
                } else {
                    item[1] = p;
                    buckets.get(w.charAt(p) - 'a').add(item);
                }
            }
        }
        return count;
    }
}

Edge cases to test

  • A word longer than s
  • A word equal to s
  • Repeated words in the list (each one counts)
  • Words needing the same letter several times in a row, like "aaa"
  • Letters of a word that never appear in s

Hints

Hint 1

Checking one word is a two-pointer scan over s. Why is doing that for every word too slow when s is long?

Hint 2

For each letter, store the sorted list of positions where it occurs in s. Then each next letter of a word can be found with a binary search for the first position after the current one.

Hint 3

Even better: scan s only once. Keep 26 buckets of words waiting for a particular letter; when you read that letter in s, every word in its bucket advances to its next letter (or is complete).

FAQ

What is the best time complexity for Number of Matching Subsequences?

Optimal (buckets of waiting words) runs in O(|s| + T) time and O(W) extra space. The scan over s is linear, and each letter of each word causes exactly one move between buckets, so T letters in total cost O(T).

Which pattern does Number of Matching Subsequences use?

It is a arrays & hashing problem that uses the hashing pattern. Other problems with the same pattern: Group Anagrams, First Unique Character in a String, Group Shifted Strings.

Is there a brute force solution for Number of Matching Subsequences?

Yes. Brute force (two pointers per word) takes O(W · (|s| + L)) time and O(1) space. Check each word on its own: walk through s with one pointer and through the word with another, advancing the word pointer whenever the characters match.

Which edge cases should I test for Number of Matching Subsequences?

A word longer than s; A word equal to s; Repeated words in the list (each one counts); Words needing the same letter several times in a row, like "aaa"; Letters of a word that never appear in s.