940. Distinct Subsequences II

Practice Distinct Subsequences II for free on NudgeCode: Hard, Dynamic Programming pattern. Write it in Python or JavaScript, run the tests in your browser, and ask for a hint when you are stuck.

Return the number of distinct non-empty subsequences of s, modulo 10^9 + 7. A subsequence keeps the relative order of the characters it takes; two subsequences are the same if they spell the same string.

Example

s = "abc"  ->  7     ("a","b","c","ab","ac","bc","abc")
s = "aba"  ->  6     ("a","b","ab","aa","ba","aba")
s = "aaa"  ->  3

Constraints