java solution using priority queue


  • 0
    2

    Time complexity: O(N + R*lg R), N = s.length(), R = 256

    public class Solution {
        public String frequencySort(String s) {
            int[] freq = new int[256];
            for (int i = 0; i < s.length(); i++) {
                freq[s.charAt(i)]++;
            }
            PriorityQueue<int[]> pq = new PriorityQueue<int[]>(256, new C());
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < 256; i++) {
                pq.add(new int[]{freq[i], i});
            }
            while (!pq.isEmpty()) {
                int[] i = pq.remove();
                char c = (char)i[1];
                while (i[0] > 0) {
                    sb.append(c);
                    i[0]--;
                }
            }
            return sb.toString();
        }
        
        class C implements Comparator<int[]> {
            public int compare(int[] i1, int[] i2) {
                return Integer.compare(i2[0], i1[0]);
            }
        }
    }
    

Log in to reply
 

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