Number of Matching Subsequences
Real-world version: Labels That Read Through the TapeThe statement here is our own: the same inputs, outputs and technique.
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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def num_matching_subseq(s: str, words: list[str]) -> int:public int numMatchingSubseq(String s, String[] words)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 10 test cases: 10 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's