Distinct Subsequences
Real-world version: Ways to Spell the MotifThe statement here is our own: the same inputs, outputs and technique.
trace and motif are strings of English letters. Upper case and lower case are
different letters throughout.
A pick is a set of positions in trace, read in increasing order, whose letters
spell motif exactly. Two picks count as different when their position sets
differ, even when the letters they read off are identical.
Return how many picks trace admits for motif.
Examples
Example 1
- Input
- trace = "AbAb", motif = "Ab"
- Output
- 3
The picks are positions (0,1), (0,3) and (2,3). Each reads A then b.
Example 2
- Input
- trace = "aaaa", motif = "aa"
- Output
- 6
Any two of the four positions spell the motif, and there are six such pairs.
Example 3
- Input
- trace = "aA", motif = "a"
- Output
- 1
Only position 0 holds a lower-case a; position 1 holds a different letter because case matters.
Example 4
- Input
- trace = "ab", motif = "abc"
- Output
- 0
The motif needs three positions and the trace only offers two, so no pick exists.
Constraints
- 1 <= trace.length, motif.length <= 1000
- trace and motif consist of English letters.
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_distinct(trace: str, motif: str) -> int:public int numDistinct(String trace, String motif)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 13 test cases: 13 passed
- Passed: 4 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