class Solution { // Greedy solution implementing PriorityQueue public int minDeletions(String s) { int maxChar = 25; HashMap<Character, Integer> freq = new HashMap(maxChar); PriorityQueue<Integer> pq = new PriorityQueue(maxChar, new Comparator<Integer>(){ public int compare(Integer o1, Integer o2){ return o2 - o1; } }); // Characters to delete int delCount = 0; // Add characters to Map for(int i = 0; i < s.length(); i++){ char c = s.charAt(i); if(!freq.containsKey(c)) freq.put(c, 1); else freq.put(c, freq.get(c) + 1); } //for(Map.Entry entry : freq.entrySet()) //System.out.println(entry.getKey() + ":" + entry.getValue()); // Add character frequencies to PriorityQueue for(Map.Entry entry : freq.entrySet()) pq.add((Integer) entry.getValue()); // Traverse PriorityQueue while(!pq.isEmpty()){ //printQ(pq); // store topmost entry int top = pq.peek(); // remove topmost entry pq.remove(); if(pq.isEmpty()) break; if(top == pq.peek()){ if(top > 1) // insert decremented top entry pq.add(top - 1); // increment character deletion count delCount++; } } return delCount; } public void printQ(PriorityQueue<Integer> pq){ for(Integer i : pq) System.out.print(i +","); System.out.println(); } }
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter