1241. Distinct Subsequences II

HardDynamic ProgrammingString DP

Given a string s, count the distinct non-empty subsequences of s. Two subsequences are the same if they produce identical strings, regardless of which positions were used. Return the count modulo 1000000007. The input is JSON {s}.

Input: JSON {s}.

Output: Integer — the number of distinct non-empty subsequences modulo 1e9+7.

Examples

Example 1 
Input: {"s":"abc"}
Output: 7
Explanation: a, b, c, ab, ac, bc, abc.
Example 2 
Input: {"s":"aba"}
Output: 6
Explanation: a, b, ab, ba, aa, aba.
Example 3 
Input: {"s":"aaa"}
Output: 3
Explanation: a, aa, aaa.

Constraints

Asked by

AmazonGoogle
Solve this problem in the editor →