Concise Java solution using Heap and Pair


  • 0
    B
    public class Solution {
        
        public class Pair implements Comparable<Pair>{
            char c; 
            int count;
            public Pair(char c, int count){
                this.c = c;
                this.count = count;
            }
            @Override
            public int compareTo(Pair o){
                return o.count != count ? o.count - count : o.c - c;
            }
        }
        
        public String rearrangeString(String str, int k) {
            if(k <= 1) return str;
            
            Map<Character, Integer> count = new HashMap<Character,Integer>();
            PriorityQueue<Pair> pairHeap = new PriorityQueue<Pair>();
            Queue<Pair> voidPairs = new LinkedList<Pair>();
            StringBuilder res = new StringBuilder();
            
            for(int i=0; i<str.length(); i++) count.put(str.charAt(i), count.getOrDefault(str.charAt(i), 0) + 1);
            for(char c : count.keySet()) pairHeap.add(new Pair(c, count.get(c)));
            
            for(int i=0; i<str.length(); i++){
                if(voidPairs.size() == k) pairHeap.add(voidPairs.remove());
                if(pairHeap.isEmpty()) return "";
                Pair chosen = pairHeap.peek();
                if(chosen.count == 0) return "";
        
                res.append(chosen.c);
                voidPairs.add(chosen);
                pairHeap.remove();
                chosen.count--;
            }
            return res.toString();
        }
    }
    

Log in to reply
 

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