Number of Matching Subsequences

Medium
639.

Number of Matching Subsequences

Number of Matching Subsequences is a medium coding problem on strings, binary search and two pointers, asked in Amazon, Google and Meta interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @param {string[]} words
 * @return {number}
 */
var numMatchingSubseq = function(s, words) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Number of Matching Subsequences — Problem & Solution

Number of Matching Subsequences solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Number of Matching Subsequences is a medium coding problem on strings, binary search and two pointers, asked in Amazon, Google and Meta interviews.

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.

Hints for Number of Matching Subsequences

  1. Hint 1

    Testing one word is a simple two-pointer walk: advance through s, ticking off the word's characters in order.

  2. Hint 2

    Doing that per word is O(|s| · |words|), which is the straightforward answer and fine at these limits.

  3. Hint 3

    The faster route buckets the words by their next needed character and sweeps s once, moving each waiting word forward as its character arrives.

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

  1. For each word, set a pointer i at its start.
  2. Walk s once; whenever the current character of s equals word[i], advance i.
  3. The word matches if i reaches the end of the word.
  4. 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))

Java

public static int numMatchingSubseq(String s, String[] words) {
    int total = 0;
    for (String w : words) {
        int i = 0;
        for (int j = 0; j < s.length() && i < w.length(); j++) {
            if (s.charAt(j) == w.charAt(i)) i++;
        }
        if (i == w.length()) total++;
    }
    return total;
}

C++

int numMatchingSubseq(string s, vector<string>& words) {
    int total = 0;
    for (const string& w : words) {
        size_t i = 0;
        for (size_t j = 0; j < s.size() && i < w.size(); j++) {
            if (s[j] == w[i]) i++;
        }
        if (i == w.size()) total++;
    }
    return total;
}

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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Binary Search