Minimum Number of Keypresses

给一个可以任意摆放的keypad和一个字符串, 求如果得到这个字符串最少按几次keypad.

因为keypad只有0-9, 所以这题和频率大小有关, 贪婪算法.

class Solution {
    class Pair{
        int cnt;
        char c;
        public Pair(int cnt, char c){
            this.cnt = cnt;
            this.c = c;
        }
    }
    public int minimumKeypresses(String s) {
        int res = 0;
        Map<Character, Integer> map = new HashMap<>();
        for(char c : s.toCharArray())
            map.put(c, map.getOrDefault(c, 0) + 1);
        List<Pair> pairs = new ArrayList<>();
        for(Map.Entry<Character, Integer> entry : map.entrySet())
            pairs.add(new Pair(entry.getValue(), entry.getKey()));
        Collections.sort(pairs, (a, b) -> (b.cnt - a.cnt));
        int i = 0;
        Map<Character, Integer> keypad = new HashMap<>();
        for(Pair p : pairs) {
            map.put(p.c,(i / 9) + 1);
            i++;
        }
        for(char c : s.toCharArray())
            res += map.get(c);
        return res;
    }
}