Number of Matching Subsequences

MediumHashing · Bucketing by Next Character🧩 Hashing & Counting LeetCode #792 ↗Updated Oct 30, 2026

Problem

You get a lowercase string s and a list of lowercase strings words. Count how many entries of words are subsequences of s, i.e. can be obtained by deleting zero or more characters of s without reordering the rest. Duplicate words are counted once per occurrence.

Inputs = "abcde", words = ["a","bb","acd","ace"]Output3

Inputs = "dsahjpjauf", words = ["ahjpjau","ja","ahbwzgqnuk","tnmlanowax"]Output2

1 ≤ s.length ≤ 5·10⁴ · 1 ≤ words.length ≤ 5000 · 1 ≤ words[i].length ≤ 50

Try it yourself

Java

class Solution {
    public int numMatchingSubseq(String s, String[] words) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Instead of re-scanning s once per word, scan s once and let every word wait in a bucket keyed by the next letter it needs. Each character of s advances exactly the words waiting for it.

PatternHashing & Counting

Instinct Need "have I seen this before?", "how many times?" or "group things that look alike"? Trade memory for O(1) lookups with a HashMap, HashSet or int[26].

Memory hack Don't search, remember - every element checks in at the front desk, and the desk answers instantly.

Open the Hashing & Counting guide →

Approaches

Brute ForceTwo-Pointer Check per Word

Time O(W · |s| + L)Space O(1)

For every word walk a pointer through s, advancing the word pointer whenever the characters match. The word is a subsequence iff its pointer reaches the end. Here W = number of words, L = total word length.

Java

public int numMatchingSubseq(String s, String[] words) {
    int count = 0;
    for (String w : words) {
        if (isSubsequence(w, s)) count++;
    }
    return count;
}

private boolean isSubsequence(String w, String s) {
    int j = 0; // next character of w to match
    for (int i = 0; i < s.length() && j < w.length(); i++) {
        if (s.charAt(i) == w.charAt(j)) j++;
    }
    return j == w.length();
}

Simple greedy check, but rescans all of s for every word (~2.5·10⁸ steps worst case).

BetterIndex Lists + Binary Search

Time O(|s| + L log |s|)Space O(|s|)

Store, for each letter, the sorted list of its positions in s. To match a word, keep the last used position and binary-search the next occurrence of each letter strictly after it. A failed search means the word is not a subsequence.

Java

public int numMatchingSubseq(String s, String[] words) {
    List<List<Integer>> pos = new ArrayList<>();
    for (int c = 0; c < 26; c++) pos.add(new ArrayList<>());
    for (int i = 0; i < s.length(); i++) pos.get(s.charAt(i) - 'a').add(i);

    int count = 0;
    for (String w : words) {
        int prev = -1; // index in s of the last matched character
        boolean ok = true;
        for (int k = 0; k < w.length() && ok; k++) {
            List<Integer> list = pos.get(w.charAt(k) - 'a');
            int idx = firstGreater(list, prev);
            if (idx == list.size()) ok = false;
            else prev = list.get(idx);
        }
        if (ok) count++;
    }
    return count;
}

// smallest index i with list.get(i) > target, or list.size()
private int firstGreater(List<Integer> list, int target) {
    int lo = 0, hi = list.size();
    while (lo < hi) {
        int mid = (lo + hi) >>> 1;
        if (list.get(mid) > target) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}

Cost depends on word length, not on |s|; the log factor remains.

OptimalWaiting Buckets (Single Scan of s)

Time O(|s| + L)Space O(W)

Put each word in the bucket of its first letter as a state (word, progress). For each character c of s, take the whole bucket c, advance every state by one, and either count it (finished) or drop it into the bucket of its next needed letter. Each word character is handled once.

Java

public int numMatchingSubseq(String s, String[] words) {
    List<List<int[]>> waiting = new ArrayList<>(); // states {wordIndex, progress}
    for (int c = 0; c < 26; c++) waiting.add(new ArrayList<>());
    for (int w = 0; w < words.length; w++) {
        waiting.get(words[w].charAt(0) - 'a').add(new int[]{w, 0});
    }
    int count = 0;
    for (int i = 0; i < s.length(); i++) {
        int c = s.charAt(i) - 'a';
        List<int[]> ready = waiting.get(c);
        waiting.set(c, new ArrayList<>()); // re-queued states need a LATER char
        for (int[] st : ready) {
            st[1]++;
            String w = words[st[0]];
            if (st[1] == w.length()) count++;
            else waiting.get(w.charAt(st[1]) - 'a').add(st);
        }
    }
    return count;
}

Linear in the input size with one pass over s — the best you can do.

Pro tip

Swap in a fresh list for bucket c before processing it, otherwise a word needing c twice (like "bb") would consume one character of s twice.

At a glance

Level	Approach	Time	Space
Brute Force	Two-Pointer Check per Word	`O(W · \|s\| + L)`	`O(1)`
Better	Index Lists + Binary Search	`O(\|s\| + L log \|s\|)`	`O(\|s\|)`
Optimal	Waiting Buckets (Single Scan of s)	`O(\|s\| + L)`	`O(W)`

Common pitfalls

Re-using the same character of s for two letters of a word (e.g. counting "bb" in "abc").
Binary search for ≥ prev instead of > prev — same off-by-one bug.
Deduplicating words — duplicates must each be counted (a cache is fine, dropping them is not).

Interview tips

Start from the two-pointer subsequence check, then ask: why scan s W times?
Mention caching results of duplicate words as a cheap practical win.
Explain the bucket idea as "every word is waiting for its next letter".

Pattern

Bucket by next needed key → many patterns matched against one stream: process the stream once and advance waiting states.

My notes saved in this browser