451. Sort Characters By Frequency

/*
 * sort in decreasing order
 * get frequency table
 * walk through it once to construct max heap?
 */

class Solution {

  private class Frequency {
    public int freq;
    public char c;

    public Frequency(int freq, char c) {
      this.freq = freq;
      this.c = c;
    }
  }

  private class FrequencyComparator implements Comparator<Frequency> {
    @Override
    public int compare(Frequency a, Frequency b) {
      return a.freq - b.freq;
    }
  }

  public String frequencySort(String s) {
    if(s == null || s.length() < 2) return s;

    int[] freqMap = new int[128];

    for(int i = 0; i < s.length(); i++) {
      freqMap[s.charAt(i)]++;
    }

    PriorityQueue<Frequency> pq =
      new PriorityQueue<Frequency>(
          s.length(),
          Collections.reverseOrder(new FrequencyComparator()));

    for(int i = 0; i < freqMap.length; i++) {
      if (freqMap[i] == 0) continue;

      pq.add(new Frequency(freqMap[i], (char)i));
    }

    StringBuilder sb = new StringBuilder();

    while(pq.size() != 0) {
      Frequency f = pq.poll();
      for(int i = 0; i < f.freq; i++) {
        sb.append(f.c);
      }
    }

    return sb.toString();
  }
}