Counting Subsequences

View as PDF
Submit solution
Points: 10
Time limit: 1.0s
Memory limit: 16M
Problem type

Given a string, count all distinct subsequences (not substrings).
As defined previously, a subsequence is a collection of characters from the string (they don't have to be contiguous).

For example, for the string aba, there are 6 distinct subsequences: (a, b, aa, ab, ba, aba).

Input Specification

The string, on one line. It will consist only of lowercase letters.
It will be no longer than 100\,000 characters long (this is easier than all substrings!).

Output Specification

The number of distinct subsequences.
Note that this number may be ridiculously large, so print it \bmod 10\,007.

Comments


  • -1
    abemorgan  commented on Jan. 23, 2023, 8:56 a.m.

    I think there is an error in the question, because it states: For example, for the string aba, there are 6 distinct subsequences: (a, b, aa, ab, ba, aba). But wouldn't 'aab' and 'baa' also be distinct subsequences?