Simple HashMap Based Solution in Java


  • 0
    K

    The idea is to iterate over the string and create a mapping of character to its frequency. After this, we need to sort the map by values. Then a StringBuilder can be used to append the appropriate characters.

        public String frequencySort(String s) {
            
            Map<Character, Integer> map = new HashMap<>();
            for(Character c : s.toCharArray()) 
                map.put(c, map.getOrDefault(c, 0) + 1);
            
            List<Character> keyList = new ArrayList<>(map.keySet());
            List<Integer> valueList = new ArrayList<>(map.values());
            
            Collections.sort(valueList, Collections.reverseOrder());
            
            StringBuilder ans = new StringBuilder();
            
            for(Integer v : valueList) {
                for(Character c : keyList) {
                    if(map.get(c) == v) {
                        for(int i = 0; i < v; i++)
                            ans.append(c);
                        map.remove(c);
                        break;
                    }
                }
            }
            return ans.toString();    
        }
    

  • 0
    O

    The time complexity for your solution could be O(n^2)


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.