字符串价值

题目难度：中等

知识点：数学逻辑，字符串，数组

解题思路：每一次减去当前字符串中出现次数最多的字符，重复K次后，即可得到价值最小的字符串。

方法一

使用优先队列。首先定义一个数组，用于存储字符串中每一个字符出现的次数，然后定义一个优先队列对每一个字符出现的次数由大到小进行排列，每一次循环，对次数最大的数字减一，直至循环到第k次为止，计算所有字符串出现的次数，最后将所有次数的平方和相加。

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner in=new Scanner(System.in);
        String s=in.next();
        int k=in.nextInt();
        char[] cs = s.toCharArray();
        //定义数组，计算字符串中每一字符出现的次数
        int[] a = new int[26];
        for(char c:cs){
            a[c - 'a']++;
        }
        //定义优先队列存储字符串中字符出现的个数
        PriorityQueue<Integer> pq = new PriorityQueue<>((o1,o2)->{
            return o2 - o1;
        });
        for(int num:a){
            if(num != 0) pq.add(num);
        }
        int i = 0;
        //依次移除数量最多的字符
        while(i < k){
            int num = pq.remove();
            pq.add(num - 1);
            i++;
        }
        int sum = 0;
        for(int num:pq){
            sum += num * num;
        }
        System.out.println(sum);
    }
}

方法二

不使用优先队列。首先定义一个数组，用于存储字符串中每一个字符出现的次数，然后进行k次循环，每次循环找到数组中的最大值，并对最大值减一。循环结束后，将数组中所有值的平方和相加。

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner in=new Scanner(System.in);
        String s=in.next();
        int k=in.nextInt();
        char[] cs = s.toCharArray();
        //定义数组，计算字符串中每一字符出现的次数
        int[] a = new int[26];
        for(char c:cs){
            a[c-'a']++;
        }
        //循环找到数字中的最大值，并对最大值减一
        for(int i = 0;i<k;i++){
            int maxId = 0;
            for(int j = 0;j<26;j++){
                if(a[j]>a[maxId])
                    maxId = j;
            }
            a[maxId]--;
        }
        int res = 0;
        for(int i =0;i<26;i++){
            res+=a[i]*a[i];
        }
        System.out.println(res);
    }
}

方法三

首先，使用HashMap存储每一个字符出现的次数，然后将字符出现的次数添加进ArrayList中，并进行k次循环，每一次循环首先对ArrayList进行排序，随后对最大值进行减一处理。最后将ArrayList中所有值的平方和相加。

import java.util.*;
public class Main {
    public static void main(String[] args){
        Scanner in=new Scanner(System.in);
        String str=in.nextLine();
        int k=in.nextInt();
        //定义一个HashMap用于存储每一个字符出现的次数
        HashMap<Character,Integer> map=new HashMap();
        for(int i=0;i<str.length();i++){
            char c=str.charAt(i);
            if(!map.containsKey(c))
                map.put(c, 1);
            else{
                map.put(c, map.get(c)+1);
            }
        }
        //将字符出现的次数存储在ArrayList中
        List<Integer> list=new ArrayList(map.values());
        int a[]=new int[list.size()];
        for(int i=0;i<list.size();i++){
            a[i]=list.get(i);
        }
        //对字符的出现次数进行排序，后最大值减一
        for(int i=0;i<k;i++){
            Arrays.sort(a);
            a[a.length-1]--;
        }
        int sum=0;
        for(int i=0;i<a.length;i++)
            sum+=a[i]*a[i];
        System.out.println(sum);
    }
}