# Java Solution O(N + KlogK)

• ``````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();
}
``````

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