Java Solution O(N + KlogK)


  • 0
    C
    public String rearrangeString(String str, int k) {
            // if k == 0 then the input String is valid no re-arrangement is required.
            if(k == 0){
                return str;
            }
            
            PriorityQueue<int[]> priorityQueue = new PriorityQueue<int[]>((int[] a1, int[] a2) -> {
                // if frequency is same then sort based on char
                if(a2[1] == a1[1]){
                    return a1[0] - a2[0];
                }
                
                // sort based on max frequency
                return a2[1] - a1[1];
            });
    
            // calculating the frequency of each char (Runtime is O(N))
            int[] arr = new int[26];
            for (char c : str.toCharArray()) {
                arr[(c - 'a')]++;
            }
    
            // populating the queue (Ideally the runtime is nlogn but since n == 26 so its o(1))
            for (int i = 0; i < arr.length; i++) {
                if (arr[i] > 0) {
                    priorityQueue.offer(new int[] { i, arr[i] });
                }
            }
            
            // Stored characters which can be used for later use.
            Queue<int[]> queue = new LinkedList<int[]>();
            boolean cannotBeArranged = false;
    
            StringBuilder result = new StringBuilder();
    
            // since priority queue at max can be 26 in length so iterating through this is O(1)
            while (!priorityQueue.isEmpty() && !cannotBeArranged) {
                
                // Runtime is O(k)
                for (int i = 0; i < k; i++) {
                    
                    if (priorityQueue.isEmpty()) {
                        // if there is no charaters to be used for later use (queue is empty) then we obtained result.
                        if(!queue.isEmpty()){
                            cannotBeArranged = true;
                        }
                        break;
                    }
    
                    int[] top = priorityQueue.poll();
                    result.append((char) (top[0] + 'a'));
    
                    if (--top[1] > 0) {
                        queue.offer(top);
                    }
                }
                
                // at max this can be K size so runtime is klogk
                while (!queue.isEmpty()) {
                    priorityQueue.offer(queue.poll());
                }
            }
    
            return cannotBeArranged ? "" : result.toString();
        }
    

Log in to reply
 

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