Number of distinct sums of substrings problem

Revision en2, by fofao_funk, 2017-09-11 03:51:17

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


  Rev. Lang. By When Δ Comment
en2 English fofao_funk 2017-09-11 03:51:17 42
en1 English fofao_funk 2017-09-11 03:49:51 732 Initial revision (published)