Hi all.

Can someone give me some tips on how to solve the following problem?

Given a non-empty string *S* consisting of lowercase letters with length at most 10^{5}, calculate the number of distinct sums for every substring of *S*. The sum of a string is defined as the sum of the values of all the characters in it. The values of the characters are in the range [1, 26], starting from *a*; i.e., the value of *a* is 1, the value of *b* is 2 and so on.

For example, the distinct sums for the string *S* = *acd* are 1, 3, 4, 7, 8; in this case, the answer should be 5.

This problem is from brazilian first subregional, which occurred yesterday, and the given time limit was 7 seconds.

Thanks for the help!