有一种有趣的字符串价值计算方式:统计字符串中每种字符出现的次数,然后求所有字符次数的平方和作为字符串的价值
例如: 字符串"abacaba",里面包括4个'a',2个'b',1个'c',于是这个字符串的价值为4 * 4 + 2 * 2 + 1 * 1 = 21
牛牛有一个字符串s,并且允许你从s中移除最多k个字符,你的目标是让得到的字符串的价值最小。
输入包括两行,第一行一个字符串s,字符串s的长度length(1 ≤ length ≤ 50),其中只包含小写字母('a'-'z')。 第二行包含一个整数k(0 ≤ k ≤ length),即允许移除的字符个数。
输出一个整数,表示得到的最小价值
aba 1
2
str, N = input(), int(input()) dic = {} for c in str: if dic.__contains__(c) : dic[c] += 1 else : dic[c] = 1 vs = list(dic.values()) #values vs.sort(reverse = True) while N > 0 : #防止N大于字符串长度 for i in range(len(vs)) : vs[i] -= 1 N -= 1 if N == 0 or i == len(vs)-1 or vs[i] >= vs[i+1] : break ret = 0 for i in vs : ret += i*i print (ret)
import java.util.*; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); String str = in.nextLine(); int n = in.nextInt(); // 存储字母和重复次数的map Map<String , Integer> map = new HashMap<>(); // 将str的每个字母都放进map for (int i = 1; i <= str.length(); i ++) { changeMap(map, str.substring(i - 1, i)); } // map按值从大到小排序 map = sortDesc(map); int count; // 每次拿出一个值最大的entry,然后减一,重复n次 for(int i = 0; i < n; i ++) { count = 0; for (String s : map.keySet()) { count ++; changeMap2(map, s); // 这是为了保证每次只拿出一个字母,肯定又更好的写法,但是目前没想到 if (count > 0) { break; } } map = sortDesc(map); } // 计算结果 int result = 0; for (Integer integer : map.values()) { result += integer * integer; } System.out.println(result); } /** * 修改map,以str为key的value值 + 1 * @param map * @param str key */ public static void changeMap(Map<String, Integer> map, String str) { if (map.containsKey(str)) { map.put(str, map.get(str) + 1); } else { map.put(str, 1); } } /** * 修改map,以str为key的值 -1 * @param map * @param str key */ public static void changeMap2(Map<String , Integer> map, String str) { map.put(str , map.get(str) - 1); } /** * 将map按值从大到小排序,核心代码 * @param map map * @return */ public static Map<String, Integer> sortDesc(Map<String, Integer> map) { List<Map.Entry<String, Integer>> list = new LinkedList<>(map.entrySet()); Collections.sort(list, new Comparator<Map.Entry<String, Integer>>() { @Override public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) { return - ((o1.getValue()).compareTo(o2.getValue())); } }); Map<String, Integer> returnMap = new LinkedHashMap<>(); for (Map.Entry<String, Integer> e : list) { returnMap.put(e.getKey(), e.getValue()); } return returnMap; } }