Rearrange String k Distance Apart

Hard · Heap / Priority Queue · Explanation and code example

Greedy

How it works

Instead of simulating character placement one by one, we can think of the problem in terms of segments. If the maximum frequency of any character is maxFreq, we need at least maxFreq segments. Characters with the highest frequency must appear in every segment, while those with lower frequencies can be distributed across fewer segments.

The idea is to first place all high-frequency characters (those appearing maxFreq or maxFreq - 1 times) into their respective segments, ensuring they are spaced apart. Then, distribute the remaining characters in a round-robin fashion across the first maxFreq - 1 segments.

For the arrangement to be valid, each of the first maxFreq - 1 segments must have at least k characters. The last segment can be shorter since no character needs to maintain distance after it.

Steps

  1. Count the frequency of each character and find the maximum frequency maxFreq.
  2. Identify characters with frequency equal to maxFreq (most frequent) and maxFreq - 1 (second most frequent).
  3. Create maxFreq segments. Place one instance of each "most frequent" character in every segment, and one instance of each "second most frequent" character in all but the last segment.
  4. Distribute the remaining characters (those with frequency less than maxFreq - 1) across the first maxFreq - 1 segments in round-robin order.
  5. Verify that each of the first maxFreq - 1 segments has at least k characters. If not, return an empty string.
  6. Concatenate all segments and return the result.

Complexity

  • Time complexity: O(N)
  • Space complexity: O(K)

Where N is the length of the string s, and K is the number of unique characters in the string s.

Things to watch for

Ignoring the Edge Case When k Equals Zero or One

When k is 0 or 1, any arrangement is valid since there is no spacing constraint. Failing to handle these cases early can lead to division by zero errors (e.g., segmentId % (maxFreq - 1)) or unnecessary processing.

Reinserting Characters to Priority Queue with Stale Frequencies

In the priority queue approach, after using a character, its frequency decreases. When reinserting it from the cooldown queue back to the priority queue, you must use the updated frequency, not the original. Using stale frequencies causes incorrect ordering and wrong character selection.

Miscalculating the Cooldown Period

The cooldown constraint means the same character cannot appear within k positions of its last occurrence. A common error is using k-1 instead of k for the cooldown check, or vice versa. Carefully verify that (currentIndex - lastUsedIndex) >= k before reusing a character.

Not Detecting Impossible Cases Early

If the maximum frequency character appears more times than can be accommodated given k and the string length, rearrangement is impossible. Failing to detect this early leads to infinite loops or incorrect outputs. Check that each segment (except possibly the last) can contain at least k characters.

Off-by-One Errors in Segment Distribution

When distributing characters across segments in the greedy approach, the last segment has different requirements than the others. Forgetting to skip the last segment when placing maxFreq - 1 frequency characters, or using wrong modular arithmetic for round-robin distribution, causes incorrect results.

Python code example

from collections import Counter

class Solution:
    def rearrangeString(self, s: str, k: int) -> str:
        freqs = Counter(s)
        max_freq = max(freqs.values()) if freqs else 0

        # Store all the characters with the highest and second highest frequency
        most_chars = set()
        second_chars = set()

        for char, freq in freqs.items():
            if freq == max_freq:
                most_chars.add(char)
            elif freq == max_freq - 1:
                second_chars.add(char)

        # Create max_freq number of different strings
        segments = [[] for _ in range(max_freq)]

        # Insert one instance of characters with frequency max_freq & max_freq - 1 in each segment
        for i in range(max_freq):
            for c in most_chars:
                segments[i].append(c)

            # Skip the last segment as the frequency is only max_freq - 1
            if i < max_freq - 1:
                for c in second_chars:
                    segments[i].append(c)

        segment_id = 0

        # Iterate over the remaining characters and distribute instances over segments
        for char, freq in freqs.items():
            # Skip characters with max_freq or max_freq - 1 frequency
            if char in most_chars or char in second_chars:
                continue

            # Distribute the instances over segments in round-robin manner
            for _ in range(freq):
                segments[segment_id].append(char)
                segment_id = (segment_id + 1) % (max_freq - 1)

        # Each segment except the last should have exactly k elements
        for i in range(max_freq - 1):
            if len(segments[i]) < k:
                return ""

        # Join all segments and return
        return ''.join(''.join(segment) for segment in segments)

C++ code example

class Solution {
public:
    string rearrangeString(string s, int k) {
        unordered_map<char, int> freqs;
        int maxFreq = 0;
        // Store the frequency, and find the highest frequency.
        for (char c : s) {
            freqs[c]++;
            maxFreq = max(maxFreq, freqs[c]);
        }

        unordered_set<char> mostChars;
        unordered_set<char> secondChars;
        // Store all the characters with the highest and second highest frequency - 1.
        for (pair<char, int> charPair: freqs) {
            if (charPair.second == maxFreq) {
                mostChars.insert(charPair.first);
            } else if (charPair.second == maxFreq - 1) {
                secondChars.insert(charPair.first);
            }
        }

        // Create maxFreq number of different strings.
        string segments[maxFreq];
        // Insert one instance of characters with frequency maxFreq & maxFreq - 1 in each segment.
        for (int i = 0; i < maxFreq; i++) {
            for (char c: mostChars) {
                segments[i] += c;
            }

            // Skip the last segment as the frequency is only maxFreq - 1.
            if (i < maxFreq - 1) {
                for (char c: secondChars) {
                    segments[i] += c;
                }
            }
        }

        int segmentId = 0;
        // Iterate over the remaining characters, and for each, distribute the instances over the segments.
        for (pair<char, int> charPair: freqs) {
            char currChar = charPair.first;

            // Skip characters with maxFreq or maxFreq - 1
            // frequency as they have already been inserted.
            if (mostChars.find(currChar)  != mostChars.end()
                || secondChars.find(currChar) != secondChars.end()) {
                continue;
            }

            // Distribute the instances of these characters over the segments in a round-robin manner.
            for (int freq = freqs[currChar]; freq > 0; freq--) {
                segments[segmentId] += charPair.first;
                segmentId = (segmentId + 1) % (maxFreq - 1);
            }
        }

        // Each segment except the last should have exactly K elements; else, return "".
        for (int i = 0; i < maxFreq - 1; i++) {
            if (segments[i].size() < k) {
                return "";
            }
        }

        string ans;
        // Join all the segments and return them.
        for (string s : segments) {
            ans += s;
        }

        return ans;
    }
};
Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations