The O(n) Club: Number of Matching Subsequences: Parading Your Words With Buckets, Not Regret

The O(n) Club: Number of Matching Subsequences — Parading Your Words With Buckets, Not Regret

⚡ TL;DR

You get a string s and an array of words. Count how many of those words are subsequences of s—which means each letter shows up in order, skipping is ok, but backtracking gets you ejected from the parade. Brute-force works until your program falls asleep. Clever devs use buckets so every character and word gets moved only once, like a conga line with a point.
Here’s the “please don’t interview this way” brute force version:

// Brute force. You have been warned.
int numMatchingSubseq(String s, String[] words) {
    int count = 0;
    for (String word : words) {
        int i = 0, j = 0;
        while (i < s.length() && j < word.length()) {
            if (s.charAt(i) == word.charAt(j)) j++;
            i++;
        }
        if (j == word.length()) count++;
    }
    return count;
}

🧠 How Devs Usually Mess This Up

First, you scan every word for a match—over, and over, and over. Congratulations! You’ve invented a slow, sad for-loop that times out on LeetCode faster than you can type Runtime Error. It’s like running a spelling bee where every contestant recites the dictionary, for every question.

🔍 What’s Actually Going On

Imagine every word you want to check is a float in a tech parade, just waiting for its favorite letter. Line each up in a bucket matching the next letter it needs. As you touch each character in s, every float in the bucket parades forward to its next wanted letter (or finishes and goes home to confetti). Only one pass for the string, and each word steps forward at most as many times as it has letters. Fancy footwork—and efficient as servers running after hours.

🛠️ PseudoCode

• Make 26 buckets, one for every lowercase letter. Each holds a queue of word iterators (“WordNode”—which word, and which letter it’s waiting for).
• For every word, place it in the bucket for its first character.
• Walk through each character in s:
  • Take the matching bucket for that character.
  • For each waiting word (grab original queue size):

    WordNode wn = queue.poll();
    wn.pos++;
    if (wn.pos == wn.word.length()) count++;
    else buckets.get(wn.word.charAt(wn.pos) - 'a').offer(wn);

• Words that reach the end are winners. Everyone else keeps walking or drops out quietly.

💻 The Code

class Solution {
    static class WordNode {
        String word;
        int pos;
        WordNode(String w, int p) { word = w; pos = p; }
    }
    public int numMatchingSubseq(String s, String[] words) {
        List<queue>> buckets = new ArrayList<>();
        for (int i = 0; i < 26; i++) buckets.add(new ArrayDeque<>());
        for (String w : words) {
            buckets.get(w.charAt(0) - 'a').offer(new WordNode(w, 0));
        }
        int count = 0;
        for (char c : s.toCharArray()) {
            Queue
<wordnode> q = buckets.get(c - 'a');
            int n = q.size();
            while (n-- > 0) {
                WordNode node = q.poll();
                node.pos++;
                if (node.pos == node.word.length()) count++;
                else buckets.get(node.word.charAt(node.pos) - 'a').offer(node);
            }
        }
        return count;
    }
}</wordnode></queue>

⚠️ Pitfalls, Traps & Runtime Smacks

• Duplicates? Yes, you count every instance. If a word is repeated, so is your joy.
• Empty words count as subsequences of anything. If you see a lot, ask who wrote the test cases.
• Case sensitivity: Only lowercase letters, or you’ll throw an index-out-of-bounds parade instead.
• Complexity: Every character in s and each word’s character is processed at most once. Speed: O(length of s + total letters in words). Space: Worth it.

🧠 Interviewer Brain-Tattoo

When in doubt, bucket your problems—not your tears. (And never brute-force what you can bucket. Trust me, your CPU is watching.)