DSUBSEQ - Distinct Subsequences
Given a string, count the number of distinct subsequences of it ( including empty subsequence ). For the uninformed, A subsequence of a string is a new string which is formed from the original string by deleting some of the characters without disturbing the relative positions of the remaining characters.
For example, "AGH" is a subsequence of "ABCDEFGH" while "AHG" is not.
Input
First line of input contains an integer T which is equal to the number of test cases. You are required to process all test cases. Each of next T lines contains a string s.
Output
Output consists of T lines. Ith line in the output corresponds to the number of distinct subsequences of ith input string. Since, this number could be very large, you need to output ans%1000000007 where ans is the number of distinct subsequences.
Example
Input: 3 AAA ABCDEFG CODECRAFT Output: 4 128 496
Constraints and Limits
T ≤ 100, length(S) ≤ 100000
All input strings shall contain only uppercase letters.
hide comments
|
pradeep_7:
2020-10-11 07:22:32
Approach :
|
|
manish_thakur:
2020-05-22 19:29:49
good problem , beware of mod of negative values |
|
mrmajumder:
2020-04-21 13:13:22
Beware of negative values, if you're getting wa for modding |
|
mrmajumder:
2020-04-21 13:13:06
Beware of negative values, if you're getting wa for modding |
|
cpp219:
2020-01-29 04:17:21
good problem :) |
|
hetp111:
2020-01-15 19:08:48
how do you do these kinds of dp problems by top down method ? |
|
nyawriter:
2019-12-28 12:44:39
Negative value.. |
|
somz22:
2019-05-31 14:40:40
Try to do it in O(n), not O(26*n) it's possible just make dp relation properly. |
|
aj_254:
2019-05-06 11:17:37
solvable in python play ez .not much optimization required just use dp and standard input output |
|
f00zz:
2019-04-30 12:24:11
@deepak097 thanks for spoiling the problem :( |
Added by: | Ajay Somani |
Date: | 2008-02-05 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: CPP |
Resource: | CodeCraft 08, Problem Setter: Jin Bin |