358. Rearrange String k Distance Apart


Problem Description

The given problem involves taking a string s and an integer k. The task is to rearrange the characters of the string in such a way that the same characters in the new string are separated by at least k distances from each other. If it is not possible to perform such a rearrangement that satisfies the condition, the output should be an empty string "".

For example, If we have the string s = "aabbcc" and k = 3, one possible rearrangement could be "abcabc", as any same characters are at least k = 3 units apart. However, if k was larger, say 7, it would be impossible to rearrange because we don't have enough unique characters to place between repeats to satisfy the distance requirement.

Intuition

To find a solution to this problem, we need a way to ensure that whenever we add characters to the new string (let's call it ans), we respect the minimum distance k between the same characters.

One intuitive approach is to keep track of the frequency of each character and always pick the character with the highest remaining frequency that doesn't violate the k distance rule. To efficiently select the highest frequency characters, we can use a max-heap. In Python, we use a min-heap with negative frequencies to simulate a max-heap.

However, simply using a max-heap isn't enough, because we must wait until k different characters have been added to ans before we're allowed to use the same character again. For this, we can use a queue to temporarily store characters and their adjusted frequencies after they've been used. By the time a character circles back from the end of the queue to the front, k other characters would have been placed in ans, allowing us to either discard the character if its frequency has dropped to zero or push it back into the heap with an adjusted (decremented) frequency to potentially use it again.

The process continues until the heap is empty, meaning all characters have been used up. If at the end of this process the length of ans is not equal to the length of s, that would mean it was not possible to rearrange the string to satisfy the condition, and therefore we return an empty string. Otherwise, we concatenate the characters in ans and return the rearranged string.

Learn more about Greedy, Sorting and Heap (Priority Queue) patterns.

Solution Approach

The solution uses a combination of a max-heap (implemented as a min-heap with negated values in Python) and a queue for efficient character selection and distancing. Here's a step-by-step breakdown:

  1. Frequency Counting: We start by counting the frequency of each character in s using the Counter from the collections module. This gives us a dictionary of characters along with their respective frequencies.

  2. Heap Initialization: We then convert this dictionary into a list of tuples, where each tuple contains the negated frequency of the character and the character itself ((-v, c)). This list is then turned into a heap using heapify, which organizes it so that the character with the highest frequency (lowest negative number) is at the top of the heap.

  3. Queue Initialization: A queue is initialized using deque to store characters after they are popped from the heap, along with their adjusted (decremented) frequency.

  4. String Construction: We then enter a loop to construct the answer string:

    • Pop the character with the highest frequency from the heap (or the least negative number since we are using a min-heap).
    • Negate its frequency back to positive and add the character to the answer list ans.
    • Add the character and its decremented frequency (frequency - 1) to the queue to make it wait until we've placed k characters between its repetitions.
  5. Maintaining the Distance k: For every character added to ans, we check if the queue has reached length k. If it has, we pop from the queue's left (the front), which would be the character that was put there k steps ago.

    • If this character's frequency is still more than 0 (meaning it needs to be placed again), we push it back into the heap with its frequency negated to maintain the max-heap property.
  6. Final Check and Result: Once the heap is empty, we check if the length of the ans list is the same as the input string s. If they're not equal, it indicates that it was impossible to arrange s according to the given condition, and we return an empty string "". Otherwise, we join the list ans into a string and return it as the final answer.

By using a heap, we ensure that we always pick the character with the highest frequency that isn't currently "on hold" in the queue, which maximizes our chances of finding a valid character placement. The queue, on the other hand, ensures that each character is placed far enough apart to meet the condition specified by k.

Here's the key code component breakdown:

  • Counter(s).items() gives us character frequencies.
  • heapify(h) turns our list h into a heap.
  • heappop(h) retrieves and removes the highest frequency character from the heap.
  • q.append((v - 1, c)) adds characters to the queue.
  • q.popleft() removes and returns the leftmost character from the queue.
  • heappush(h, (-w, c)) pushes a character back into the heap with its updated frequency.

This algorithm ensures that we can efficiently arrange characters k apart in the optimal way, or determine that such an arrangement is not possible.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

How would you design a stack which has a function min that returns the minimum element in the stack, in addition to push and pop? All push, pop, min should have running time O(1).

Example Walkthrough

Let's walk through a small example to illustrate the solution approach using the string s = "aaabc" and k = 2.

  1. Frequency Counting: Count the frequency of each character.

    1'a': 3
    2'b': 1
    3'c': 1
  2. Heap Initialization: Initialize the heap with negated frequencies to simulate max-heap.

    1Heap: [(-3, 'a'), (-1, 'b'), (-1, 'c')]
    2(This is turned into a heap in-place, so it might not look ordered here.)
  3. Queue Initialization: Initialize an empty queue with deque.

    1Queue: []
  4. String Construction: Let's start constructing the string. The heap contains the following elements (negated frequencies shown):

    1Step 1: Pop 'a' (real frequency 3) and add to answer -> ans = ['a'], Heap now: [(-1, 'b'), (-1, 'c')]
    2Step 2: Pop 'b' (real frequency 1) and add to answer -> ans = ['a', 'b'], Heap now: [(-1, 'c')]
    3Step 3: We cannot pop 'a' again since it's only 1 character away, but we can pop 'c'.
    4         Add 'c' to answer -> ans = ['a', 'b', 'c'], Heap now: []

    At this point, the heap is temporarily empty, but we still have characters to reinsert. Our queue keeps track of the characters we've used.

  5. Maintaining the Distance k: After each character addition to ans, we push it into the queue with a decremented frequency if it's greater than 0.

    1Step 1: Push ('a', 2) into the queue
    2Step 2: Push ('b', 0) into the queue
    3Step 3: Since 'b' frequency is now 0, we don't push it again, but we push ('c', 0)

    Once 'a' has been in the queue for k = 2 steps, we pop it from the queue. Its adjusted frequency is larger than 0, so we reinsert ('a', 2) into the heap.

  6. Final Check and Result: We continue this process, and our ans looks like this at the end: ['a', 'b', 'c', 'a', 'a']. We compare the length of ans with s, and they're not equal, which means a valid arrangement was not possible. Thus, we return an empty string "".

However, if at some step a different character had a frequency sufficient to complete the process, such as 'd', we might have arranged 'd' in between and the process could return a valid string. For this example, since it's not possible to meet the requirement of placing the same characters k = 2 distances apart due to high frequency of 'a', we return an empty string.

This concludes the example walkthrough, illustrating how the combination of a max-heap and a queue helps to solve the problem of arranging characters at least k distance apart or determining that it's not feasible.

Solution Implementation

1from collections import Counter, deque
2from heapq import heapify, heappop, heappush
3
4class Solution:
5    def rearrangeString(self, s: str, k: int) -> str:
6        # If k is 0 or 1, no rearrangement is needed, just return the original string.
7        if k <= 1:
8            return s
9      
10        # Create a max heap based on the frequency of characters in the string
11        # where the most frequent character is at the top.
12        # Negate the frequency counts as Python has a min-heap by default.
13        frequency_heap = [(-frequency, char) for char, frequency in Counter(s).items()]
14        heapify(frequency_heap)
15      
16        # Use a queue to keep track of characters that have been used, to maintain
17        # the distance of 'k' between the same characters.
18        wait_queue = deque()
19
20        # This list will contain the rearranged characters.
21        rearranged_string = []
22
23        # Process the heap until all characters are rearranged.
24        while frequency_heap:
25            # Pop the character with the highest frequency.
26            frequency, char = heappop(frequency_heap)
27            # Reverse the negation to get the positive frequency count.
28            frequency = -frequency
29          
30            # Append the character to the result.
31            rearranged_string.append(char)
32          
33            # Record the character in the queue with its updated frequency,
34            # to be pushed back into the heap when it's allowed (after 'k' placements).
35            wait_queue.append((frequency - 1, char))
36          
37            # If the waiting queue has 'k' elements, it's time to add an element back
38            # to the heap (if it still has a non-zero frequency).
39            if len(wait_queue) == k:
40                wait_frequency, wait_char = wait_queue.popleft()
41                if wait_frequency > 0:
42                    heappush(frequency_heap, (-wait_frequency, wait_char))
43
44        # If the length of the rearranged string equals the original string length,
45        # return the rearranged string as it's valid. Otherwise, return an empty string.
46        return "".join(rearranged_string) if len(rearranged_string) == len(s) else ""
47
1class Solution {
2    public String rearrangeString(String s, int k) {
3        // Length of the input string
4        int stringLength = s.length();
5
6        // Array to keep track of character counts
7        int[] charCounts = new int[26];
8
9        // Count the frequency of each character in the string
10        for (char ch : s.toCharArray()) {
11            ++charCounts[ch - 'a'];
12        }
13
14        // Priority Queue to store character frequencies and sort them in descending order
15        PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a, b) -> b[0] - a[0]);
16
17        // Add character counts to the Priority Queue
18        for (int i = 0; i < 26; ++i) {
19            if (charCounts[i] > 0) {
20                maxHeap.offer(new int[] {charCounts[i], i});
21            }
22        }
23
24        // Queue to keep track of characters used in the last k positions
25        Deque<int[]> queue = new ArrayDeque<>();
26
27        // StringBuilder to build the result string
28        StringBuilder result = new StringBuilder();
29
30        // Loop until the Priority Queue is empty
31        while (!maxHeap.isEmpty()) {
32            int[] current = maxHeap.poll(); // Get the most frequent remaining character
33            int count = current[0];
34            int charIndex = current[1];
35
36            // Add the character to the result
37            result.append((char) ('a' + charIndex));
38            // Decrease the count and add character to queue
39            queue.offer(new int[] {count - 1, charIndex});
40
41            // If there are k elements in queue, it's time to release the front element
42            if (queue.size() >= k) {
43                int[] front = queue.pollFirst();
44                if (front[0] > 0) {
45                    // If it still has remaining count, add it back to the Priority Queue
46                    maxHeap.offer(front);
47                }
48            }
49        }
50
51        // Check if the result string's length is same as the input string
52        // If not, return empty string as it's not possible to rearrange
53        return result.length() == stringLength ? result.toString() : "";
54    }
55}
56
1#include <string>
2#include <queue>
3#include <unordered_map>
4
5using namespace std;
6
7class Solution {
8public:
9    string rearrangeString(string str, int k) {
10        // If k is 0, rearrangement isn't needed
11        if (k == 0) {
12            return str;
13        }
14
15        // Count the occurrences of each character
16        unordered_map<char, int> char_count;
17        for (char ch : str) {
18            ++char_count[ch];
19        }
20
21        // Priority queue to store characters based on their frequency
22        priority_queue<pair<int, char>> max_heap;
23        for (auto& pair : char_count) {
24            max_heap.push({pair.second, pair.first});
25        }
26
27        // Queue to keep track of the cooldown for recently used characters
28        queue<pair<int, char>> cooldown_queue;
29        string result;
30
31        while (!max_heap.empty()) {
32            auto [freq, ch] = max_heap.top();
33            max_heap.pop();
34
35            // Append the current character to the result string
36            result += ch;
37          
38            // Decrease the frequency and add character to cooldown queue
39            cooldown_queue.push({freq - 1, ch});
40
41            // If cooldown queue size reached k, release the front character from cooldown
42            if (cooldown_queue.size() >= k) {
43                auto [freq_count, front_char] = cooldown_queue.front();
44                cooldown_queue.pop();
45
46                // If the character still has remaining counts, add it back to the max heap
47                if (freq_count > 0) {
48                    max_heap.push({freq_count, front_char});
49                }
50            }
51        }
52
53        // If result size is different from input string size, rearrangement is not possible
54        return result.size() == str.size() ? result : "";
55    }
56};
57
1import { PriorityQueue } from 'typescript-collections'; // Assuming PriorityQueue from a collection library
2
3// Type for Character Frequency
4type CharFrequency = [number, string];
5
6// A custom comparator for the PriorityQueue which is needed for max heap functionality
7function maxHeapComparator(a: CharFrequency, b: CharFrequency): number {
8  return b[0] - a[0]; 
9}
10
11// Function to rearrange the string based on frequency of characters
12// and minimum distance (k) between same characters
13function rearrangeString(str: string, k: number): string {
14  // If k is 0, there is no need to rearrange the string
15  if (k === 0) {
16    return str;
17  }
18
19  // Map to count the occurrences of each character
20  const charCount: Record<string, number> = {};
21  for (const ch of str) {
22    if (!charCount[ch]) {
23      charCount[ch] = 0;
24    }
25    charCount[ch]++;
26  }
27
28  // Max heap to store characters based on their frequency
29  const maxHeap = new PriorityQueue<CharFrequency>(maxHeapComparator);
30  for (const ch in charCount) {
31    maxHeap.enqueue([charCount[ch], ch]);
32  }
33
34  // Queue to keep track of the cooldown for recently used characters
35  const cooldownQueue: CharFrequency[] = [];
36  let result = '';
37
38  while (!maxHeap.isEmpty()) {
39    const [freq, ch] = maxHeap.dequeue();
40
41    // Append the current character to the result string
42    result += ch;
43
44    // Decrease the frequency, if any left then add character to cooldown queue
45    if (freq - 1 > 0) {
46        cooldownQueue.push([freq - 1, ch]);
47    }
48
49    // If cooldown queue size is greater or equal to k, release front character from cooldown
50    if (cooldownQueue.length >= k) {
51      const [frontFreq, frontCh] = cooldownQueue.shift();
52      // If the character still has remaining frequency, add it back to the max heap
53      if (frontFreq > 0) {
54        maxHeap.enqueue([frontFreq, frontCh]);
55      }
56    }
57  }
58
59  // If the result size is different from input string size, rearrangement is not possible
60  return result.length === str.length ? result : '';
61}
62
63// Assuming you have a PriorityQueue implementation, if not you will need to get or implement one
64// Note: The syntax "import { PriorityQueue } ..." assumes there is a PriorityQueue class available 
65// in the 'typescript-collections' library. You may need to replace this with actual import path
66// or you could implement your own priority queue with a max heap property.
67

Time and Space Complexity

Time Complexity

The time complexity of this function is predominantly determined by the operations associated with the heap and the deque.

  • The construction of the heap occurs once using heapify after converting the Counter(s).items() into a list of tuples, which takes O(n) time, where n is the number of distinct characters in the string s.
  • The main while-loop runs as long as there are elements in the heap, which means it can execute up to len(s) times because in the worst case each letter is appended to the answer string ans.
  • Inside the loop, the heappop operations happen once per loop iteration, which has a complexity of O(log n), as each heappop operation is on a heap of at most n distinct characters.
  • Adding an element back into the heap has the same O(log n) complexity for the same reasons.
  • The operations associated with the deque, such as append and popleft, both operate in O(1) time.

Since each character passes through the heap and the deque at most once, the heappop and the heappush operations dominate. Thus, the overall time complexity of the main loop is O(len(s) * log n), where len(s) is the length of the input string and n is the number of distinct characters.

Space Complexity

The space complexity of this function is dominated by the heap, the deque, and the output list.

  • The heap can contain at most n elements, where n is the number of distinct characters in s.
  • The deque can contain at most k elements since we insert one element per loop iteration and remove one when the deque size exceeds k.
  • The output list ans will ultimately contain len(s) elements.

Combining these factors, the space complexity can be considered O(n + k + len(s)). However, since n and k are bounded by the length of s, this can be simplified to O(len(s)), which is the overhead required to store the answer separate from the input.

In conclusion:

  • Time Complexity: O(len(s) * log n)
  • Space Complexity: O(len(s))

Learn more about how to find time and space complexity quickly using problem constraints.


Fast Track Your Learning with Our Quick Skills Quiz:

In a binary min heap, the maximum element can be found in:


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Coding Interview Strategies

Dive into our free, detailed pattern charts and company guides to understand what each company focuses on.

See Patterns

🪄