We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Rearrange String k Distance Apart

Number: 358

Difficulty: Hard

Paid? Yes

Companies: Amazon, TikTok, Google

Problem Description

Given a string s and an integer k, rearrange s such that the same characters are at least distance k from each other. If it is not possible to rearrange the string to meet this constraint, return an empty string "".

Key Insights

  • The frequency of each character dictates the feasibility and placement within the rearrangement.
  • A greedy approach picks the most frequent available character to maximize the chance of successful placement.
  • A max-heap (priority queue) efficiently selects the highest frequency character each time.
  • A waiting queue ensures that once a character is used, it can't be reused until k positions later.
  • Special case: When k is 0, no rearrangement is required because all orders satisfy the condition.

Space and Time Complexity

Time Complexity: O(n log C) where n is the length of s and C is the number of unique characters.
Space Complexity: O(n) due to the storage used for the heap and wait queue.

Solution

We use a greedy algorithm with a max-heap to always select the character with the highest remaining frequency that is currently available. The algorithm first counts the frequency of each character and pushes these into a max-heap (using negative frequencies for languages like Python where heapq is a min-heap). Each time a character is selected, it is appended to the result string and its frequency is decreased. This character is then placed in a waiting queue to ensure it isn’t reused until k positions later. Once the waiting period completes, if the character still has remaining occurrences, it is reinserted into the heap. If at any point the heap is empty and the waiting queue still contains characters that haven't been reinserted while the result string is incomplete, we conclude that a valid rearrangement is impossible.

Code Solutions

from collections import Counter, deque
import heapq

def rearrangeString(s: str, k: int) -> str:
    if k == 0:
        return s  # No rearrangement needed if k is 0
    
    # Count the frequency of each character
    char_count = Counter(s)
    
    # Build a max-heap using negative frequencies
    max_heap = [(-freq, ch) for ch, freq in char_count.items()]
    heapq.heapify(max_heap)
    
    # Queue to keep track of characters waiting for k distance
    wait_queue = deque()
    result = []
    
    # Process the heap until it's empty
    while max_heap:
        freq, ch = heapq.heappop(max_heap)
        result.append(ch)
        
        # Decrease frequency (remember freq is negative)
        freq += 1
        
        # Add current char to the wait queue
        wait_queue.append((freq, ch))
        
        # If we've placed k characters, we can re-insert the oldest one if needed
        if len(wait_queue) < k:
            continue
        
        freq_front, ch_front = wait_queue.popleft()
        if freq_front < 0:
            heapq.heappush(max_heap, (freq_front, ch_front))
    
    rearranged = ''.join(result)
    return rearranged if len(rearranged) == len(s) else ""
← Back to All Questions