Count Hidden Copies of a Pattern
A log line s may contain a pattern p spread out over it. Count the number of different ways to pick positions i1 < i2 < ... < ik in s so that the characters at those positions spell p exactly (that is, the number of times p appears as a subsequence of s).
Return the count modulo 1000000007. An empty pattern appears exactly once in any string.
Example 1
Input: s = "banana", p = "ban" Output: 3 Explanation: b at 0, then a at 1 or 3 followed by a later n.
Example 2
Input: s = "aaaa", p = "aa" Output: 6 Explanation: Choose any 2 of the 4 letters.
Constraints
- 0 <= s.length <= 3000
- 0 <= p.length <= 1000
- Lowercase letters only
Hint 1
Let ways[j] be the number of ways to form the first j characters of p using the part of s seen so far.
Hint 2
For each new character of s, update ways[j] += ways[j - 1] for matching j, going from high j to low so each character is used once.
Discussion 0
Join free to post in the discussion.
Good practice for: Data Scientist, Machine Learning Engineer, AI Engineer (LLM & Generative AI), Backend Developer, Data Engineer
Run checks your code on 3 sample tests. Submit runs all 8 tests, including hidden ones, and earns points. Use console.log to debug. Python's first run can take a few seconds while it starts.