O(n) Java Solution with Comments


  • 0
    V
    public class Solution {
        public String frequencySort(String s) {
            // Build a map of character to its frequency in the string
            Map<Character, Integer> map = new HashMap<>();
            for (char c: s.toCharArray()) {
                map.put(c, map.getOrDefault(c, 0) + 1);
            }
            // Create an array where the index represents the character's occurrence frequency
            List<Character>[] bucket = new List[s.length() + 1];
            for (Character key: map.keySet()) {
                int frequency = map.get(key);
                if (bucket[frequency] == null) {
                    bucket[frequency] = new ArrayList<>();
                }
                bucket[frequency].add(key);
            }
            // Iterate from the end of the array to the beginning
            // Append each character according to its frequency
            StringBuilder sb = new StringBuilder();
            for (int i = bucket.length - 1; i >= 0; i--) {
                if(bucket[i] != null) {
                    for (char c: bucket[i]) {
                        for (int j = 0; j < map.get(c); 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.