# Priority Queue of custom class O(n) time

• It's good to practice priority queue and comparator. The idea is to get the valid characters from priority queue for the highest character count. If there is no valid character but not finished, then return ""
Use another linked list to hold all the invalid characters at the moment and pop it back to priority queue when it become valid next pass

Time = O(n*log_2(26)) = O(n) where n is the length of string

``````public class Solution {
// character and count pairs
class CharCnt {
char c;
int cnt;
public CharCnt(char c, int cnt) {
this.c = c;
this.cnt = cnt;
}
}
public String rearrangeString(String str, int k) {
int[] cMap = new int[26];
char[] sArray = str.toCharArray();
// count all the characters
for (int i = 0; i < sArray.length; ++i) {
cMap[sArray[i]-'a']++;
}
// compare character count, see below
Comparator<CharCnt> comparator = new CharCntComparator();
PriorityQueue<CharCnt> p = new PriorityQueue<CharCnt>(comparator);
// time O(1)
for (int i = 0; i < 26; ++i) {
if (cMap[i] > 0) {
}
}
StringBuilder sb = new StringBuilder();
while (!p.isEmpty()) {
CharCnt tmp = p.poll();
// append valid character with most count
sb.append(tmp.c);
tmp.cnt -= 1;
// make it invalid for k rounds
if (sb.length() >= k) {
// pop the head of the list and put it back to queue
CharCnt tcc = kList.pollFirst();
if (tcc != null && tcc.cnt != 0) {
}
}
}
// check if the work finished
while (kList.size() > 0) {
if (kList.pollFirst().cnt != 0) {
return "";
}
}
return sb.toString();
}
class CharCntComparator implements Comparator<CharCnt> {
@Override
public int compare(CharCnt x, CharCnt y) {
return y.cnt-x.cnt;
}
}
}``````

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