hardDynamic Programming 1DAI-applied~30 min
Count Distinct Subsequences of a Token String
To estimate how many distinct prompt fragments can be sampled from a token string, count its distinct non-empty subsequences (order preserved, duplicates collapsed).
Problem
Given a string s, return the number of distinct non-empty subsequences of s, modulo 1e9 + 7. Two subsequences are the same if they are equal as strings, regardless of which positions produced them.
Input
A string s of lowercase English letters.
Output
An integer: the count of distinct non-empty subsequences modulo 1e9 + 7.
Constraints
- 1 <= s.length <= 2000
- s consists of lowercase English letters.
Examples
Example 1
Input
s = "abc"
Output
7
a, b, c, ab, ac, bc, abc.
Example 2
Input
s = "aba"
Output
6
a, b, ab, ba, aa, aba (the duplicate 'a' is counted once).