Leetcode 767 Reorganize String

You can solve this problem by using a max-heap (priority queue) to always try to place the most frequent character at each position, ensuring that no two adjacent characters are the same. Here’s how you can implement it:

1. First, count the frequency of each character.
2. Use a max-heap to keep track of characters by their frequency.
3. Greedily place characters one by one while ensuring no two adjacent characters are the same.

Here’s the complete solution:

import heapq
from collections import Counter

class Solution:
    def reorganizeString(self, s: str) -> str:
        # Step 1: Count the frequency of each character
        char_count = Counter(s)
        
        # Step 2: Create a max heap based on frequency (negative to simulate max heap with heapq)
        max_heap = [(-count, char) for char, count in char_count.items()]
        heapq.heapify(max_heap)
        
        # Step 3: The result array where we will build the solution
        result = []
        
        # Step 4: Keep track of the previous character used (we start with None)
        prev_count, prev_char = 0, ''
        
        while max_heap:
            # Pop the most frequent character
            count, char = heapq.heappop(max_heap)
            
            # Add the previous character back to the heap if it still has remaining occurrences
            if prev_count < 0:
                heapq.heappush(max_heap, (prev_count, prev_char))
            
            # Append the current character to the result
            result.append(char)
            
            # Decrease the count (since we have used one occurrence of this character)
            prev_count, prev_char = count + 1, char  # count + 1 because it's a negative number in max heap
            
        # Step 5: Join the result array into a string and check if it is valid
        result_str = ''.join(result)
        if len(result_str) != len(s):
            return ""
        return result_str

Explanation:

1. Frequency Count: We use collections.Counter to count how many times each character appears in the input string.
2. Max-Heap: We push the characters into a heap based on their frequency (negative to simulate a max heap). The most frequent characters will always come first.
3. Greedy Placement: In each iteration, we pop the most frequent character and append it to the result. We then push the previous character back into the heap if it still has remaining occurrences.
4. Validity Check: If the length of the final string does not match the input string, it means we couldn’t create a valid arrangement, and we return an empty string.

Time Complexity:

• O(n log k), where n is the length of the string, and k is the number of unique characters. This is because we insert and pop from the heap, which takes O(log k) time.

Example:

sol = Solution()
print(sol.reorganizeString("aab"))  # Output: "aba"
print(sol.reorganizeString("aaab")) # Output: ""