Number of Matching Subsequences — Medium Problem & Solution

Given a string s and an array of strings words, return how many entries of words are subsequences of s.

Difficulty: Medium
Topics: Strings, Two Pointers, Binary Search
Asked at: Amazon, Google, Meta
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given a string s and an array of strings words, return how many entries of words are subsequences of s.

A subsequence is formed by deleting zero or more characters without reordering the rest. Duplicates in words are counted separately.

Example 1

Input: s = "codekairo", words = ["code","kai","ckr","xyz"]
Output: 3
Explanation: "code", "kai" and "ckr" can all be read left to right inside s; "xyz" cannot.

Example 2

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

Example 3

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

Constraints

1 <= s.length <= 50000
1 <= words.length <= 5000
1 <= words[i].length <= 50
All strings consist of lowercase English letters.

How to solve Number of Matching Subsequences

A word is a subsequence when a greedy left-to-right match consumes all of it: always take the earliest possible occurrence of the next needed character.

Approach

For each word, set a pointer i at its start.
Walk s once; whenever the current character of s equals word[i], advance i.
The word matches if i reaches the end of the word.
Count the matching words.

Why it works

The greedy match is optimal: if any embedding exists, taking the earliest occurrence of each character leaves at least as much of s available for the rest, so the greedy walk succeeds whenever some embedding does.

Complexity

Time — O(|s| · |words|) for the direct method; O(|s| + total word length) with the bucketing trick
Space — O(1) for the direct method

Pitfalls

Checking s.includes(word) tests for a substring, which is a different (stricter) relation.
Restarting the scan of s for each character of the word is quadratic per word.

Reference solution

Python

from typing import List

def numMatchingSubseq(s: str, words: List[str]) -> int:
    def is_sub(w: str) -> bool:
        i = 0
        for c in s:
            if i < len(w) and c == w[i]:
                i += 1
        return i == len(w)
    return sum(1 for w in words if is_sub(w))

JavaScript

var numMatchingSubseq = function(s, words) {
    var isSub = function(w) {
        var i = 0;
        for (var j = 0; j < s.length && i < w.length; j++) {
            if (s.charAt(j) === w.charAt(i)) i++;
        }
        return i === w.length;
    };
    var total = 0;
    for (var t = 0; t < words.length; t++) {
        if (isSub(words[t])) total++;
    }
    return total;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 282 strings problems · the whole catalogue