Leecode 451 string frequency

A HashMap can only be used to sort keys. You could have specialized the Map as a List and then implemented an anonymous inner class using the Collections sort method.

class Solution {
    public String frequencySort(String s) {
        HashMap<Character,Integer> map = new HashMap<>();
        String res = "";
        char[] cs = s.toCharArray();
        for(Character c:cs){
            int frequency = map.getOrDefault(c,0) +1;
            map.put(c,frequency);
        }
        List<Map.Entry<Character,Integer>> list =  new ArrayList<>(map.entrySet());
        Collections.sort(list,new Comparator<Map.Entry<Character,Integer>>(){
            public int compare(Map.Entry<Character,Integer> o1,Map.Entry<Character,Integer> o2){
                returno2.getValue()-o1.getValue(); }});for(Map.Entry<Character,Integer> e:list) {
            for(int i=0; i<e.getValue(); i++) { res+=(e.getKey()+""); }}returnres; }}Copy the code

Time complexity O(n+ klogkN + KlogKN +klogk)

• First, a for loop fills the map with a string of length N, O(n);
• The Collections sort is O(klogk), where K is the number of different characters
• And finally combine the string O(n)

Space complexity O(n+ K) as long as the hash table, array, result string space

There are better methods to solve the problem including general sorting, which will not be described here