# O(log(26)*N) solution, can be applied to other characters

• The time complexity of two auxiliary array method is actually (O(26*n)). This solution is (O(log(26)*n). However, due to the overhead of creating new data structure and hashing collision, the real time cost is actually higher than the two auxiliary array method....

``````public class Solution {
public String rearrangeString(String str, int k) {
//greedy: we want to first arrange the character which has maximum number of remaining chars
Map<Character, Integer> mapCount = new HashMap<>();
//O(n)
for (int i = 0; i < str.length(); i++) {
mapCount.put(str.charAt(i), mapCount.getOrDefault(str.charAt(i),0) + 1);
}

//priority queue, ranking by the remaining counts.
//O(log(26))
PriorityQueue<Map.Entry<Character, Integer>> pq = new PriorityQueue<>((obj1, obj2) -> {
if (obj2.getValue() != obj1.getValue()) return obj2.getValue() - obj1.getValue();
else return obj1.getKey() - obj2.getKey();});

//tmpQueuue, when the character still can not be put back to the string because of lacking of distance, put
//it in this temperory queue

//run the algorithm
StringBuilder sb = new StringBuilder();
//O(log(26) * n)
while (!pq.isEmpty()) {
//get the character with largest remaining counts
Map.Entry<Character,Integer> entry = pq.poll();
entry.setValue(entry.getValue() - 1);
sb.append(entry.getKey());
//after the operation, add it to the tmp queue
tmpQ.offer(entry);

//if the character has at least k distance, put it back to the pq
if (tmpQ.size() < k) continue;
Map.Entry<Character, Integer> top = tmpQ.poll();
//put the character back to the pq only if it still has remaing counts.
if (top.getValue() > 0) pq.offer(top);
}

return sb.length() == str.length() ? sb.toString() : "";
}
}
``````

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