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⁵, 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!