Rearrange String K Distance Apart - Leetcode Solution

Problem statement:

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 "".

Example 1:

Input: s = "aabbcc", k = 3 Output: "abcabc"

Explanation: The same letters are at least distance 3 from each other.

Example 2:

Input: s = "aaabc", k = 3 Output: ""

Explanation: It is not possible to rearrange the string.

Solution:

Approach:

• Use a dictionary to store the frequency of each character in the string.
• Create a max heap to store the characters in decreasing order of their frequency.
• Initialize an empty result string.
• Loop until the heap is empty:
  • Create a temp list to store the characters in the current window of size k.
  • Loop k times and pop the character from the heap with the highest frequency.
    • If the heap is empty and the temp list is not of size k, return an empty string.
    • If the heap is empty and the temp list is of size k, add the characters back to the heap and break the loop.
    • Add the popped character to the result string and decrement its frequency in the dictionary.
    • If the frequency is not zero, add the character to the temp list.
  • If the temp list is of size k, add the characters back to the heap.
• Return the result string.

Code:

Here's the Python3 implementation of the above approach:

import heapq from collections import defaultdict

class Solution: def rearrangeString(self, s: str, k: int) -> str: # Step 1: Create dictionary to store frequency of characters freq = defaultdict(int) for char in s: freq[char] += 1

    # Step 2: Create max heap to store characters in decreasing order of frequency
    heap = [(-val, key) for key, val in freq.items()]
    heapq.heapify(heap)
    
    # Step 3: Initialize empty result string
    result = ""
    
    # Step 4: Loop until heap is empty
    while heap:
        temp_list = []
        # Loop k times to get characters for current window of size k
        for i in range(k):
            # If heap is empty and temp list is not of size k, return empty string
            if not heap and len(temp_list) != k:
                return ""
            # If heap is empty and temp list is of size k, add characters back to heap and break loop
            elif not heap and len(temp_list) == k:
                break
            # Pop character with highest frequency from heap
            freq, char = heapq.heappop(heap)
            # Add popped character to result string and decrement its frequency in dictionary
            result += char
            freq += 1
            # If frequency of character is not zero, add to temp list
            if freq != 0:
                temp_list.append((freq, char))
        # Add characters back to heap if temp list is of size k
        for item in temp_list:
            heapq.heappush(heap, item)
    
    # Return the result string
    return result

Complexity Analysis:

Time complexity: O(nlogn), where n is the length of the string s. Creating the dictionary and the heap takes O(n) time, while the loop that fills the result string takes O(nlogn) time.

Space complexity: O(n). The frequency dictionary and heap can take up to O(n) space.

1