Star-studded Lockdown
/

Hashing Algorithm

Problem
Editorial
Analytics

Amongst the lockdown and all the hassles, there is a Professor – Professor Oak, who spends his time watching stars in the sky.

One day Professor Oak saw alphabets appearing on the stars. He was so fascinated by them that he started making a list of numbers and for every new star, he inserted a number X into the list. This X is equal to the no. of times the alphabet on the current star has previously appeared.

After seeing N stars, he decided to stop and calculate the sum of all the N numbers.

Professor Oak has spent all his life watching stars and do not know how to add. Can you help him in finding the sum?

Input:

• The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
• The first line contains a single integer – N, denoting the number of stars.
• The next line contains a string S of length N, describing the characters that appeared on the N stars sequentially.

Output:

For each query, print a single line containing one integer – the sum of all the N numbers.

Constraints:

• 1 < T < 105
• 1 < N < 105
• S contains lowercase English alphabets only
• Sum of N over all test cases does not exceed 106

Test Files:

Test File #1 (10 points):

• 1 < T < 100
• 1 < N < 100

Test File #2 (20 points):

• S = { ‘a’, ‘b’ }

Test File #3 (70 points): original constraints

SAMPLE INPUT
1
5
abaab
SAMPLE OUTPUT
4
Explanation

There are 5 stars.

The list (say L) is initially empty.
L = {}.

The 1st star had alphabet ‘a’ on it. Since ‘a’ has not appeared previously, 0 is inserted in the list.
L = {0}.

The 2nd star had alphabet ‘b’ on it. Since ‘b’ has not appeared previously, 0 is inserted in the list.
L = {0, 0}.

The 3rd star had alphabet ‘a’ on it. Since ‘a’ has previously appeared 1 time, 1 is inserted in the list.
L = {0, 0, 1}.

The 4th star had alphabet ‘a’ on it. Since ‘a’ has previously appeared 2 times, 2 is inserted in the list.
L = {0, 0, 1, 2}.

The 5th star had alphabet ‘b’ on it. Since ‘b’ has previously appeared 1 time, 1 is inserted in the list.
L = {0, 0, 1, 2, 1}.

Sum of all elements in L = 4.

Time Limit: 5.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

Contributors

Initializing Code Editor...