Count Hidden Copies
Problem
A watermark mark is hidden in a longer text text if you can pick characters of text, in order, that spell mark. Two hidden copies are different if they use a different set of positions in text.
Return the number of different hidden copies of mark in text, modulo 1,000,000,007. An empty mark is hidden exactly once.
Example 1
- Input:
- text = "banana", mark = "ban"
- Output:
- 3
b at 0, then a at 1 with n at 2 or 4, or a at 3 with n at 4.
Example 2
- Input:
- text = "aaaa", mark = "aa"
- Output:
- 6
Any 2 of the 4 positions: C(4, 2) = 6.
Constraints
- 0 ≤ mark.length ≤ text.length ≤ 1000
- Both strings contain lowercase English letters only.
Hint
Show the first hint
Process text one character at a time and ask, for every prefix of mark, how many ways it has been spelled so far.
Walkthrough
How to approach it
01Clarify before coding
- Are copies distinguished by positions, not by content? Yes; all copies spell the same word.
- What does an empty mark return? 1 (choose nothing).
- Why the modulo? 'a' × 1000 choose 10 is about 2.6 · 10^23.
02Brute force
Enumerate every set of len(mark) positions in text and check whether they spell mark.
Cost: O(C(n, k) · k): for n = 1000, k = 10 that is about 2.6 · 10^23 sets.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.