Concise Java solution using bucket sort


  • 0
    D

    Time: O(n). Can replace map with int[256].

    public String frequencySort(String s) {
        // Store each character's counts
        Map<Character, Integer> map = new HashMap<>();
        int max = 0;
        for (char c : s.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0) + 1);
            max = Math.max(max, map.get(c));
        }
        StringBuilder sb = new StringBuilder();
        // Append character according by frequency
        for (int i = max ; i > 0 ; i--) {
            for (Character c : map.keySet()) {
                if (i == map.get(c)) {
                    for (int j = 0 ; j < i ; j++)
                        sb.append(c);
                }
            }
        }
        return sb.toString();
    }

Log in to reply
 

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