0984MediumArrayHash TableStringBinary SearchDynamic ProgrammingTrieSorting

Labels That Read Through the Tape

Tracked in this browser only

Trains the technique from

LeetCode 792Number of Matching Subsequences

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A tape reads s, and a list of labels is given as words.

A label reads through the tape when its characters can be found on the tape in order, though not necessarily next to each other.

Return how many of the labels read through the tape, counting a label once for each time it appears in the list.

Examples

Example 1

Input: s = "abcbadcbc", words = ["abc", "acb", "bcd", "cba", "abcd", "zz"]
Output: 5

Four of the six read through: "abc", "acb", "bcd" and "cba" can each be found in order along the tape. The label "abcd" cannot, and "zz" has no letters on the tape at all.

Example 2

Input: s = "abc", words = ["abc", "abc", "abc"]
Output: 3

The same label appears three times and each occurrence counts.

Example 3

Input: s = "a", words = ["aa"]
Output: 0

The tape holds only one a, so a label needing two cannot read through.

Constraints

1 <= s.length <= 5 * 10^4
1 <= words.length <= 5000
1 <= words[i].length <= 50
s and every entry of words consist of lowercase English letters only

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def num_matching_subseq(s: str, words: list[str]) -> int:

Java

public int numMatchingSubseq(String s, String[] words)

The intended approach

Time O(n + total) for a tape of length n and total label length.Space O(total) for the piles.

Checking each label against the tape on its own means reading the whole tape once per label, which is far too much when there are thousands of labels. Instead read the tape once and carry all the labels along with it. Hold each label in a pile named by the character it is waiting for, starting with every label in the pile for its own first character. Then walk the tape and, at each character, take that pile away whole: every label in it has just matched a character, so it either finishes, which counts, or moves into the pile for its next character. A label only ever moves forward, so the total work is the tape's length plus the labels' lengths added together.

Pythonentry point: num_matching_subseq

def num_matching_subseq(s, words):
    piles = {}
    for word in words:
        piles.setdefault(word[0], []).append((word, 0))
    matched = 0
    for ch in s:
        waiting = piles.get(ch)
        if not waiting:
            continue
        piles[ch] = []
        for word, at in waiting:
            nxt = at + 1
            if nxt == len(word):
                matched += 1
            else:
                piles.setdefault(word[nxt], []).append((word, nxt))
    return matched

The obvious version

Take each label in turn and walk the tape from the start, stepping the label forward whenever the characters agree, counting the label if it runs out. Costs the tape's length per label and carries nothing between them.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_num_matching_subseq(s, words):
    matched = 0
    for word in words:
        at = 0
        for ch in s:
            if at < len(word) and word[at] == ch:
                at += 1
        if at == len(word):
            matched += 1
    return matched

How this problem was checked

Reference solution executed against 10 test cases — 10 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in