Rearrange String k Distance Apart

Problem

Given a non-empty string s and an integer k, rearrange the string such that the same characters are at least distance k from each other.

All input strings are given in lowercase letters. If it is not possible to rearrange the string, return an empty string "".

Examples

Example 1:

1
2
3
Input: s = "aabbcc", k = 3
Output: "abcabc"
Explanation: The same letters are at least distance 3 from each other.

Example 2:

1
2
3
Input: s = "aaabc", k = 3
Output: ""
Explanation: It is not possible to rearrange the string.

Example 3:

1
2
3
Input: s = "aaadbbcc", k = 2
Output: "abacabcd"
Explanation: The same letters are at least distance 2 from each other.

Solution

Method 1 - Using maxheap

Here is the approach:

Frequency Counting: Count the frequency of each character in the string.
Max-Heap (Priority Queue): Use a max-heap to always fetch the most frequent character first.
Queue for Positioning: Use a queue to manage and ensure that characters are placed k distance apart.
Rebuild the String: Build the result string by appending characters, respecting the distance constraint.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public class Solution {
    public String rearrangeString(String s, int k) {
        if (k == 0) return s;

        Map<Character, Integer> freqMap = new HashMap<>();
        for (char c : s.toCharArray()) {
            freqMap.put(c, freqMap.getOrDefault(c, 0) + 1);
        }

        PriorityQueue<Map.Entry<Character, Integer>> maxHeap = new PriorityQueue<>(
            (a, b) -> b.getValue() - a.getValue());

        maxHeap.addAll(freqMap.entrySet());

        Queue<Map.Entry<Character, Integer>> waitQueue = new LinkedList<>();
        StringBuilder result = new StringBuilder();

        while (!maxHeap.isEmpty()) {
            Map.Entry<Character, Integer> current = maxHeap.poll();
            result.append(current.getKey());
            current.setValue(current.getValue() - 1);
            waitQueue.offer(current);

            if (waitQueue.size() >= k) {
                Map.Entry<Character, Integer> front = waitQueue.poll();
                if (front.getValue() > 0) {
                    maxHeap.offer(front);
                }
            }
        }

        return result.length() == s.length() ? result.toString() : "";
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def rearrangeString(self, s: str, k: int) -> str:
        if k == 0:
            return s

        freq_map = Counter(s)
        max_heap = [(-value, key) for key, value in freq_map.items()]
        heapq.heapify(max_heap)
        
        queue = deque()
        result = []

        while max_heap:
            value, key = heapq.heappop(max_heap)
            result.append(key)
            queue.append((key, value + 1))

            if len(queue) >= k:
                front = queue.popleft()
                if front[1] < 0:
                    heapq.heappush(max_heap, front)

        return "".join(result) if len(result) == len(s) else ""

Complexity

⏰ Time complexity: O(n log n), where n is the length of the string. This is due to heap operations, which are O(log n), and we perform these operations n times.
🧺 Space complexity: O(n), due to the space used by the frequency map, the heap, and the queue.

Problem#

Examples#

Solution#

Method 1 - Using maxheap#

Code#

Complexity#