Skip to content

Instantly share code, notes, and snippets.

@dmnugent80
Created October 28, 2018 20:15
Show Gist options
  • Save dmnugent80/f9d0bda3df0c364b4b4b9ea44848a7b7 to your computer and use it in GitHub Desktop.
Save dmnugent80/f9d0bda3df0c364b4b4b9ea44848a7b7 to your computer and use it in GitHub Desktop.
PriorityQueue sort HashMap by value - character frequency
class Solution {
public String frequencySort(String s) {
if (s.length() < 1) return "";
Map<Character, Integer> charMap = new HashMap<>();
for (char ch : s.toCharArray()) {
Integer count = charMap.get(ch);
if (count != null) {
charMap.put(ch, count + 1);
} else {
charMap.put(ch, 1);
}
}
PriorityQueue<CharWithCount> pq = new PriorityQueue(charMap.size(), new Comparator<CharWithCount> () {
@Override
public int compare(CharWithCount c1, CharWithCount c2) {
return c2.mCount - c1.mCount;
}
});
for (char ch : charMap.keySet()) {
int count = charMap.get(ch);
pq.offer(new CharWithCount(ch, count));
}
StringBuilder sb = new StringBuilder();
while (!pq.isEmpty()) {
CharWithCount cwc = pq.poll();
for (int i = 0; i < cwc.mCount; i++) {
sb.append(cwc.mChar);
}
}
return sb.toString();
}
class CharWithCount {
public int mCount;
public char mChar;
public CharWithCount(char ch, int count) {
mChar = ch;
mCount = count;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment