Problem statement

https://leetcode.com/problems/rearrange-string-k-distance-apart/

Solution

Evaluate frequencies of each letter. Use greedy algorithm when we build our string: each next symbol is the element with higher frequency so far. We can keep elements and their frequencies in heap to be able to extract maximum in $O(\log M)$, where $M$ is number of different symbols. When we use element, we can not use it for $k-1$ next steps, so we remove it from our heap and we will add it back in $k$ steps. We have heap and buffer, which is queue of last k elements.

On each step we extract element with the biggest frequency, update it (add +1, because we have negative values in heap), update answer and put element to buffer. Then we check if buffer size is to big and if it is, we pop element from left, we can not work with this element, put it to heap if its frequency is not equal to $0$. If at some moment heap is empty and we still need elements to proceed, return ""

Complexity

Both steps can be done in $O(\log M)$, so overall time complexity is $O(n\log M)$. Each moment of time we have no more than $M = 26$ elements in our heap.

Code

class Solution:
    def rearrangeString(self, s, k):
        if k == 0: return s
        
        c, res = Counter(s), ""
        heap = [(-c[key], key) for key in c]
        heapq.heapify(heap)
        buffer, rest = deque(), len(heap)
        
        while rest != 0:
            if heap:
                freq, symb = heapq.heappop(heap)
                freq += 1
                if freq == 0: rest -= 1
                res += symb
                buffer.append((freq, symb))
                
            if len(buffer) == k:
                freq, symb = buffer.popleft()
                if freq < 0:
                    heapq.heappush(heap, (freq, symb))

            if not heap and rest > 0:
                return ""
        
        return res

Solution 2

If we have only $M = 26$ size alphabet, we can just use array with $26$ elements to store chars’ count and its next available position. Every round, we iterate through the arrays and find out the available char with max count.

Complexity

Complexity is $O(M\cdot N)$ which is theoretically bigger, but in practice works faster.\

Code

class Solution:
    def rearrangeString(self, s, k):
        if k == 0: return s
        
        freq, units, queue, ans = [0]*26, 0, deque(), ""

        for elem in s:
            freq[ord(elem) - ord("a")] += 1
        
        rest = len(Counter(s))
        
        while rest != 0:
            if len(queue) == k:
                old = queue.popleft()
                if old < 26: freq[old] *= (-1)
                    
            max_freq = max(freq)
            max_freq_ind = freq.index(max(freq))
            
            if max_freq == 0: return ""
            
            freq[max_freq_ind] = 1 - freq[max_freq_ind]
            if freq[max_freq_ind] == 0: rest -= 1
            ans += chr(max_freq_ind + 97)
            queue.append(max_freq_ind)
        
        return ans

Remark

This problem is very similar to problem 0621. Task Scheduler