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
m_alhussein_96:
2016-08-19 06:59:29
why I can't solve it top-down ? |
|
Avik Sarkar:
2016-08-16 09:50:23
Be Careful With MOD .. The subtraction you are doing to remove the multiple occurrences may cause a negative result . That's why you have make it Positive . |
|
singh1495:
2016-06-22 06:52:59
ACCEPTED in first go such a nice ques... takes time but nice dp |
|
akshayvenkat:
2016-05-29 18:04:54
what is the maximum length of input string? |
|
kshubham02:
2016-05-26 21:43:02
Thank you @PRANJIT BHARALI! Your comment saved me! I had totally forgotten about the MOD, got WA and was going mad testing different self-made test cases.
|
|
praval_singhal:
2016-05-17 15:23:51
Misread Max String Length as 10,000. Got SegFault. AC in 2nd Attempt. :) |
|
Megreli:
2016-05-12 12:47:02
I have o(n) solution in Java and getting TLE :\
|
|
top34051:
2016-04-19 07:57:18
The best!! |
|
Archit Jain:
2016-04-15 15:39:14
really nice DP |
|
lakshay_v06:
2016-03-24 09:17:58
Woaaahhh! Gr8 Question. Done in O(n) :) .... Thanks to Shashank Tiwari for the tips! :D Last edit: 2016-03-24 09:19:35 |
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 |