小红的字母游戏（A组）

链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
 

题目描述

小红有一个长度为 nnn 的字符串 sss，仅包含小写字母，小红可以选出 kkk 个字符，组成一个新的字符串 ttt，对于 ttt 的每一个字符 tit_iti​，如果 tit_iti​ 在 ttt 中出现的次数为 yyy，则小红会获得 yyy 的分数，现在小红想知道，她最多能获得多少分。

输入描述:

第一行两个整数 n,kn,kn,k，表示字符串 sss 的长度和小红选出的字符个数。
第二行一个字符串 sss，表示小红的字符串。
1≤k≤n≤1051 \leq k \leq n \leq 10^51≤k≤n≤105

输出描述:

输出一个整数，表示小红最多能获得的分数。

示例1

输入

复制5 3 aabcc

5 3
aabcc

输出

复制5

5

说明

小红选出 "acc"，第一个字符获得 1 分，第二个字符获得 2 分，第三个字符获得 2 分，一共获得 5 分。

import java.util.*;

public class Main {

    public static void main(String args[]) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int k = in.nextInt();
        in.nextLine();
        String s = in.next();

        // 统计每个字符的频率
        int[] freq = new int[26];
        for (int i = 0; i < n; i++) {
            freq[s.charAt(i) - 'a']++;
        }

        // 对频率数组进行降序排序
        Integer[] freqWrapper = new Integer[26];
        for (int i = 0; i < 26; i++) {
            freqWrapper[i] = freq[i];
        }
        Arrays.sort(freqWrapper, Collections.reverseOrder());

        long score = 0;
        // 从最高频率开始贪心的选择字符
        for (int i = 0; i < 26 && k > 0; i++) {
            if (freqWrapper[i] < k) {
                score += (long) freqWrapper[i] * freqWrapper[i];
                k -= freqWrapper[i];
            } else {
                score += (long) k * k;
                k = 0;
            }
        }

        System.out.println(score);
    }
}

import java.util.*;
import java.io.*;
public class Main{
    static int n;
    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw=new PrintWriter(System.out);
        String[] st=  br.readLine().split(" ");
        int n=Integer.parseInt(st[0]);
        int k=Integer.parseInt(st[1]);
        char[] arr= br.readLine().toCharArray();
        int[] cnt=new int[26];
        for(int i=0;i<n;i++){
            cnt[arr[i]-'a']++;
        }
        long ans=0;
        Arrays.sort(cnt);
        for(int i=25;i>=0;i--){
            if(k>=cnt[i]){
                ans +=(long)cnt[i]*cnt[i];
            }else {
                ans +=(long)k*k;
                break;
            }
            k-=cnt[i];
        }
        pw.println(ans);
        pw.close();
    }
}