Distinct Subsequences Count
HardPractice library · +30 XPhash mapdynamic programmingstring
Given a string S, find the number of distinct non-empty subsequences of S. Since the answer can be very large, print it modulo 10^9 + 7.
Input
A single line containing the string S.
Output
A single integer, the count of distinct non-empty subsequences modulo 10^9 + 7.
Constraints
1 <= |S| <= 200000.
Time limit 1 s (native code; slower languages get more)Memory 256 MB15 hidden tests
Example 1
Input
aba
Output
6
Distinct subsequences are 'a', 'b', 'ab', 'aa', 'ba', 'aba'. Count is 6.
Example 2
Input
aaa
Output
3
Distinct subsequences are 'a', 'aa', 'aaa'. Count is 3.
Hints
Similar problems
- Longest Palindromic SubsequenceMedium
- Count Vowel OccurrencesEasy
- String with Most Unique CharactersMedium
- Count Subsequences Summing to KEasy
- Longest Substring With At Most K Distinct CharactersMedium
- Longest Substring Without RepeatsMedium
More topics: Strings problems, Hash Map and Hashing problems, Dynamic Programming problems
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
Example 1 input
aba
Example 2 input
aaa