Number of Matching Subsequences

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".

Examples

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 * 10^4
• 1 <= words.length <= 5000
• 1 <= words[i].length <= 50
• s and words[i] consist of only lowercase English letters.

Solution

Method 1 – Index Buckets + Binary Search

Intuition

For each word, we want to check if it is a subsequence of s. Instead of scanning s for each word, we preprocess s: for each character, store all its indices. For each word, for each character, use binary search to find the next occurrence after the previous character's index.

Approach

1. Preprocess s: for each character, store a sorted list of indices.
2. For each word, for each character, use binary search to find the next index in s after the previous character's index.
3. If all characters are found in order, count the word as a matching subsequence.

Code

C++

#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>
using namespace std;
class Solution {
public:
    int numMatchingSubseq(string s, vector<string>& words) {
        unordered_map<char, vector<int>> idx;
        for (int i = 0; i < s.size(); ++i) idx[s[i]].push_back(i);
        int ans = 0;
        for (auto& w : words) {
            int prev = -1, ok = 1;
            for (char c : w) {
                auto& v = idx[c];
                auto it = upper_bound(v.begin(), v.end(), prev);
                if (it == v.end()) { ok = 0; break; }
                prev = *it;
            }
            ans += ok;
        }
        return ans;
    }
};

Go

import "sort"
func numMatchingSubseq(s string, words []string) int {
    idx := make(map[byte][]int)
    for i := range s { idx[s[i]] = append(idx[s[i]], i) }
    ans := 0
    for _, w := range words {
        prev, ok := -1, true
        for i := range w {
            v := idx[w[i]]
            j := sort.Search(len(v), func(j int) bool { return v[j] > prev })
            if j == len(v) { ok = false; break }
            prev = v[j]
        }
        if ok { ans++ }
    }
    return ans
}

Java

import java.util.*;
class Solution {
    public int numMatchingSubseq(String s, String[] words) {
        Map<Character, List<Integer>> idx = new HashMap<>();
        for (int i = 0; i < s.length(); ++i) {
            idx.computeIfAbsent(s.charAt(i), k -> new ArrayList<>()).add(i);
        }
        int ans = 0;
        for (String w : words) {
            int prev = -1;
            boolean ok = true;
            for (char c : w.toCharArray()) {
                List<Integer> v = idx.getOrDefault(c, new ArrayList<>());
                int j = Collections.binarySearch(v, prev+1);
                if (j < 0) j = ~j;
                if (j == v.size()) { ok = false; break; }
                prev = v.get(j);
            }
            if (ok) ans++;
        }
        return ans;
    }
}

Kotlin

class Solution {
    fun numMatchingSubseq(s: String, words: Array<String>): Int {
        val idx = mutableMapOf<Char, MutableList<Int>>()
        for (i in s.indices) idx.getOrPut(s[i]) { mutableListOf() }.add(i)
        var ans = 0
        for (w in words) {
            var prev = -1; var ok = true
            for (c in w) {
                val v = idx[c] ?: mutableListOf()
                val j = v.binarySearch(prev+1)
                val jj = if (j < 0) -j-1 else j
                if (jj == v.size) { ok = false; break }
                prev = v[jj]
            }
            if (ok) ans++
        }
        return ans
    }
}

Python

import bisect
class Solution:
    def numMatchingSubseq(self, s: str, words: list[str]) -> int:
        idx = {}
        for i, c in enumerate(s):
            idx.setdefault(c, []).append(i)
        ans = 0
        for w in words:
            prev, ok = -1, True
            for c in w:
                v = idx.get(c, [])
                j = bisect.bisect_right(v, prev)
                if j == len(v): ok = False; break
                prev = v[j]
            if ok: ans += 1
        return ans

Rust

use std::collections::HashMap;
impl Solution {
    pub fn num_matching_subseq(s: String, words: Vec<String>) -> i32 {
        let mut idx: HashMap<char, Vec<usize>> = HashMap::new();
        for (i, c) in s.chars().enumerate() {
            idx.entry(c).or_default().push(i);
        }
        let mut ans = 0;
        for w in words {
            let mut prev = None;
            let mut ok = true;
            for c in w.chars() {
                let v = idx.get(&c).unwrap_or(&vec![]);
                let j = match prev {
                    None => v.first().cloned(),
                    Some(p) => v.iter().find(|&&x| x > p).cloned(),
                };
                if let Some(jj) = j { prev = Some(jj); } else { ok = false; break; }
            }
            if ok { ans += 1; }
        }
        ans
    }
}

TypeScript

class Solution {
    numMatchingSubseq(s: string, words: string[]): number {
        const idx: Record<string, number[]> = {};
        for (let i = 0; i < s.length; ++i) {
            const c = s[i];
            if (!idx[c]) idx[c] = [];
            idx[c].push(i);
        }
        let ans = 0;
        for (const w of words) {
            let prev = -1, ok = true;
            for (const c of w) {
                const v = idx[c] || [];
                let l = 0, r = v.length;
                while (l < r) {
                    const m = (l+r)>>1;
                    if (v[m] > prev) r = m; else l = m+1;
                }
                if (l == v.length) { ok = false; break; }
                prev = v[l];
            }
            if (ok) ans++;
        }
        return ans;
    }
}

Complexity

• ⏰ Time complexity: O(L + W*K*log L), where L = len(s), W = len(words), K = avg word length.
• 🧺 Space complexity: O(L), for the index buckets.