451. Sort Characters By Frequency

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

Example 1:

Input:
"tree"

Output:
"eert"

Explanation:
'e' appears twice while 'r' and 't' both appear once.
So 'e' must appear before both 'r' and 't'. Therefore "eetr" is also a valid answer.

Example 2:

Input:
"cccaaa"

Output:
"cccaaa"

Explanation:
Both 'c' and 'a' appear three times, so "aaaccc" is also a valid answer.
Note that "cacaca" is incorrect, as the same characters must be together.

Example 3:

Input:
"Aabb"

Output:
"bbAa"

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101

class Solution {
    int[][] heap;
    int n;
    public String frequencySort(String s) {
        heap = new int[128][];
        Arrays.fill(heap, new int[] {0, 0});
        int[] counts = new int[128];
        for (char c : s.toCharArray()) {
            counts[c]++;
        }
        
        for (int i = 0; i < counts.length; i++) {
            int count = counts[i];
            if (count != 0) {
                heap[++n] = new int[] {i, count};
                swim(n);
            }
        }

        StringBuilder sb = new StringBuilder();
        while (n > 0) {
            int[] val = delMax();
            char c = (char) val[0];
            for (int i = 0; i < val[1]; i++) {
                sb.append(c);
            }
        }
        return sb.toString();
    }
    
    // max heap propery -> parent > child; j > i
    // violates i > j
    void swim(int i) {
        int j = i / 2;
        if (j > 0 && less(j, i)) {
            swap(i, j);
            swim(j);
        }
    }
    
    void sink(int i) {
        int left = 2 * i;
        int right = 2 * i + 1;
        int largest = i;
        if (left < heap.length && !less(left, largest)) {
            largest = left;
        }
        
        if (right < heap.length && !less(right, largest)) {
            largest = right;
        }
        
        if (i != largest) {
            swap(i, largest);
            sink(largest);
        }
    }
    
    boolean less(int i, int j) {
        return heap[i][1] < heap[j][1];
    }
    
    int[] delMax() {
        int[] max = heap[1];
        heap[1] = heap[n--];
        heap[n + 1] = new int[]{0,0};
        sink(1);
        return max;
    }
    
    void swap(int i, int j) {
        int[] temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    } 
    
    public String frequencySort2(String s) {
        Map<Character, Integer> freq = new HashMap<>();
        char[] symbols = s.toCharArray();
        for (char c: symbols) {
            freq.put(c, freq.getOrDefault(c, 0) + 1);
        }
        
        Queue<Map.Entry<Character, Integer>> q 
            = new PriorityQueue<>((e1, e2) -> -Integer.compare(e1.getValue(), e2.getValue()));
        
        q.addAll(freq.entrySet());
        
        StringBuilder sb = new StringBuilder();
        
         while (!q.isEmpty()) {
            var entry = q.poll();
            // System.out.println(entry);
            for (int i = 0; i < entry.getValue(); i++) {
                sb.append(entry.getKey());
            }
        }
        
        return sb.toString();
    }
}