We keep a heap of the characters appearing in the string more then once (only 1 instance of such characters will ever be in the heap at a given time) and since the alphabet size is fixed heap operations can be considered to O(1). For our problem there will never be more then 26 elements in the heap and so heap ops can be considered constant. We order the heap on oldest seen and frequency and we keep a standard queue of the characters appearing once to be tried when no valid element can be used on the heap (last seen is closer then k, or no more elements). When we remove an element from the heap and there are still instances of that character available we add another instance of that character with the last seen index (current position) and the remaining frequency.

```
static class CharIdxPair implements Comparable<CharIdxPair> {
char c;
int lastSeenIdx, freq;
public CharIdxPair(char c, int lastSeenIdx, int freq) {
this.c = c;
this.lastSeenIdx = lastSeenIdx;
this.freq = freq;
}
public CharIdxPair(char c, int freq) {
this(c, -1, freq);
}
/**
* Elements on the heap are ordered in ascending order of last used position indices therefore enabling
* an ordering of farthest from the current position to fill. We also break ties by ordering in descending order
* elements by remaining frequency count
*
* @param v
* @return
*/
@Override
public int compareTo(CharIdxPair v) {
if(this.lastSeenIdx == v.lastSeenIdx)
return v.freq - this.freq;
else
return this.lastSeenIdx - v.lastSeenIdx;
}
}
public static String rearrangeString(String str, int k) {
char[] cstr = str.toCharArray();
int[] freq = new int[256];
PriorityQueue<CharIdxPair> pq = new PriorityQueue<>();
Queue<Character> q = new ArrayDeque<>();
int n = str.length();
for (int i = 0; i < n; i++) {
freq[cstr[i]]++;
}
Set<Character> seen = new HashSet<>();
for (int i = 0; i < n; i++) {
if (seen.contains(cstr[i])) continue;
seen.add(cstr[i]);
if (freq[cstr[i]] == 1) {
q.add(cstr[i]);
} else {
// > 1
pq.add(new CharIdxPair(cstr[i], freq[cstr[i]]));
}
}
char[] buff = new char[n];
int p = 0;
while (p < n) {
if (pq.size() == 0 && q.size() == 0) return "";
else if (pq.size() == 0) {
buff[p++] = q.poll();
continue;
}
CharIdxPair cip = pq.peek();
if (cip.lastSeenIdx >= 0 && p - cip.lastSeenIdx < k) {
if (q.size() == 0) return "";
buff[p] = q.poll();
} else {
cip = pq.poll();
buff[p] = cip.c;
freq[cip.c]--;
if (freq[cip.c] > 0) {
pq.add(new CharIdxPair(cip.c, p, freq[cip.c]));
}
}
p++;
}
return new String(buff);
}
```