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