ACM. The beauty of hj45 name ●●

HJ45 The beauty of the name ●●

describe

Give a string , The string consists only of lowercase letters , The definition of this string is “ Beauty ” It's all the letters “ Beauty ” The sum of .
Every letter has one “ Beauty ”, The scope is 1 To 26 Between . No two different letters have the same “ Beauty ”. Letters ignore case .

Give multiple strings , Calculate the maximum possible for each string “ Beauty ”.

This question contains several groups of data .

Data range ： The length of the entered name meets $1\le n\le 10000$

Input description ：

The first line is an integer N, Next N Line one string per line

Output description ：

The maximum possible beauty of each string

Example

Input ：
2
zhangsan
lisi
Output ：
192
101
explain ：
For example lisi, Give Way i Your beauty is 26,l Your beauty is 25,s Your beauty is 24,lisi Your beauty is 25+26+24+26=101.

Answer key

1. Array statistics + greedy

Traversal string , Count the frequency of letters , After completion of Statistics , Because the final result only requires a score , So there is no need to know the frequency of a letter , So sort the array from large to small , The greater the frequency , The more beautiful （ Up to 26）, Finally, calculate the total beauty .

• Time complexity ：$O(Nlen)$, You need to iterate through each letter of each string .
• Spatial complexity ：$O(len+26)$, Space required to store strings .

/* HJ45  The beauty of the name  */

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int main(){
    
    int n;
    cin >> n;
    while(n--){
    
        string str;
        cin >> str;
        vector<int> table(26, 0);
        int cnt = 0;
        for(char ch: str){
        
            if(table[ch-'a'] == 0) ++cnt;        //  Statistics frequency , And the number of letters 
            ++table[ch-'a'];
        }                                        //  Sort by frequency from large to small 
        sort(table.begin(), table.end(), [=](int a, int b){
        // greater<int>()
            return a > b;
        });
        int ans = 0, score = 26;                //  score , The greater the frequency , The higher the score 
        for(int i = 0; i < cnt; ++i){
    
            ans += table[i] * score;
            --score;
        }
        cout << ans << endl;
    }
    return 0;
}