Number of Matching Subsequences - Practice Coding Problems

Number of Matching Subsequences - Problem

Array Hash Table String Binary Search Dynamic Programming Trie Sorting Medium

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

Input & Output

Example 1 — Basic Case

$ Input: s = "abcde", words = ["a", "bb", "acd"]

› Output: 2

💡 Note: "a" is a subsequence of "abcde" (take character at index 0). "bb" is not a subsequence since we only have one 'b'. "acd" is a subsequence (take characters at indices 0, 2, 3).

Example 2 — No Matches

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

› Output: 2

💡 Note: "ahjpjau" is a subsequence of "dsahjpjauf". "ja" is a subsequence. "ahbwzgqnuk" and "tnmlanowax" are not subsequences.

Example 3 — Single Character

$ Input: s = "wordgoodgoodgoodbestword", words = ["word", "good", "best", "good"]

› Output: 4

💡 Note: All words can be found as subsequences in the string s.

Constraints

1 ≤ s.length ≤ 5 × 10⁴
1 ≤ words.length ≤ 5000
1 ≤ words[i].length ≤ 50
s and words[i] consist of only lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input

String s and array of words to check

Process

Check which words can be formed as subsequences

Output

Count of valid subsequences

Key Takeaway

🎯 Key Insight: Process multiple words together instead of checking each word individually to minimize redundant scanning of string s.

Asked in

G Google 15 a Amazon 12 f Facebook 8 M Microsoft 6

The key insight is to avoid checking each word independently against string s. Instead, process all words simultaneously using a hash map to group words by their next expected character. This reduces the time complexity from O(n×m) to O(m + n×k×log m) with binary search preprocessing. Best approach depends on input size: hash map for many short words, binary search for fewer long words.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check Each Word	O(n × m)	O(1)	For each word, scan through string s to check if it's a subsequence
Hash Map Optimization	O(m + n × k)	O(n × k)	Group words by their next expected character and process efficiently
Binary Search with Preprocessing	O(m + n × k × log m)	O(m)	Preprocess string s to enable binary search for each character position

Brute Force - Check Each Word — Algorithm Steps

Iterate through each word in words array
For each word, use two pointers to check if it's a subsequence of s
Count how many words are valid subsequences

Visualization

Tap to expand

Step-by-Step Walkthrough

Check First Word

Use two pointers to see if word matches subsequence

Check Second Word

Repeat process for next word

Count Results

Sum up all matching words

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int isSubsequence(const char* word, const char* s) {
    int i = 0;
    int wordLen = strlen(word);
    int sLen = strlen(s);
    
    for (int j = 0; j < sLen && i < wordLen; j++) {
        if (s[j] == word[i]) {
            i++;
        }
    }
    return i == wordLen;
}

int solution(const char* s, char words[][100], int wordCount) {
    int count = 0;
    for (int i = 0; i < wordCount; i++) {
        if (isSubsequence(words[i], s)) {
            count++;
        }
    }
    return count;
}

int main() {
    char s[1001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    char line[10001];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    // Simple JSON parsing for array of strings
    char words[1000][100];
    int wordCount = 0;
    
    char* start = strchr(line, '[') + 1;
    char* end = strrchr(line, ']');
    *end = '\0';
    
    char* token = strtok(start, ",");
    while (token != NULL && wordCount < 1000) {
        // Remove quotes and spaces
        while (*token == ' ' || *token == '"') token++;
        char* tokenEnd = token + strlen(token) - 1;
        while (tokenEnd > token && (*tokenEnd == ' ' || *tokenEnd == '"')) {
            *tokenEnd = '\0';
            tokenEnd--;
        }
        strcpy(words[wordCount], token);
        wordCount++;
        token = strtok(NULL, ",");
    }
    
    printf("%d\n", solution(s, words, wordCount));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × m)

For each of n words, we scan through string s of length m

✓ Linear Growth

Space Complexity

O(1)

Only using a few variables, no extra data structures

✓ Linear Space

89.4K Views

Medium Frequency

~25 min Avg. Time

2.2K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check Each Word — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler