Rearrange String K Distance Apart

Problem Description

Given a string s, rearrange the characters of s so that any two adjacent characters are not the same.

Return any possible rearrangement of s or return "" if not possible.

Naive Approach

A naive approach would be to generate all possible permutations of the string and then check if any of the permutations satisfy the condition that no two adjacent characters are the same. However, this approach is very inefficient because the number of permutations of a string of length n is n!, which grows very quickly as n increases. This is not a viable solution for any reasonable input size.

Optimal Approach

The optimal approach involves using a greedy algorithm and a priority queue (heap). The main idea is to count the frequency of each character in the string. Then, we insert the characters into a max-heap based on their frequencies. We repeatedly take the character with the highest frequency from the heap, append it to the result, and decrement its frequency. If the frequency is still greater than 0, we need to re-insert it back into the heap later. To ensure that adjacent characters are not the same, we use a waiting list to hold the characters that we have used in the previous k positions. We can adapt this approach for the k=1 constraint.

Edge Cases

• If the frequency of any character is greater than (n + 1) / 2, where n is the length of the string, it is not possible to rearrange the string such that no two adjacent characters are the same.
• Empty string: should return an empty string.
• String with only one character: should return the string itself.

Code Implementation

import heapq
from collections import Counter

def rearrange_string(s: str) -> str:
    counts = Counter(s)
    max_heap = [(-count, char) for char, count in counts.items()]
    heapq.heapify(max_heap)
    
    result = []
    
    while max_heap:
        count, char = heapq.heappop(max_heap)
        result.append(char)
        
        if len(result) >= 2 and result[-1] == result[-2]:
            return ""

        if count + 1 < 0:
            heapq.heappush(max_heap, (count + 1, char))
            
    return "".join(result) if len(result) == len(s) else ""

Big O Analysis

• Time Complexity: O(NlogN), where N is the length of the string. Building the heap takes O(N) time, and each extraction and insertion into the heap takes O(logN) time. In the worst case, we may extract and insert each character once, so the overall time complexity is O(NlogN).
• Space Complexity: O(N), where N is the length of the string. We use a hash map to store the frequency of each character and a heap to store the characters and their frequencies. In the worst case the heap could contain all characters in the string.