algoadvance

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 an empty string if no such arrangement is possible.

Example:

Input: s = "aab"
Output: "aba"

Input: s = "aaab"
Output: ""

Clarifying Questions

  1. What are the constraints on the length of s?
    • Let’s assume 1 <= len(s) <= 500.
  2. Are there any special characters or is it restricted to lowercase English letters?
    • Let’s assume it is restricted to lowercase English letters only.
  3. If there are multiple valid rearrangements, is any of them acceptable?
    • Yes, any valid rearrangement is acceptable.
  4. Should we consider case sensitivity?
    • Since the input is limited to lowercase English letters, case sensitivity is not a concern.
  5. Should we consider the efficiency of the algorithm in terms of time and space complexity?
    • Yes, the provided solution should be efficient.

Strategy

  1. Count Frequency: Use a frequency counter to count occurrences of each character in the string.
  2. Max Heap: Use a max heap (priority queue) to store characters by their frequencies in descending order.
  3. Rearrange:
    • Extract the most frequent character and append it to the resulting string.
    • Keep track of the previous character that was placed in the result to avoid placing the same character twice consecutively.
    • Place the character back into the heap (with updated frequency) if it still has remaining occurrences.
    • If the heap is empty and there are still pending characters, return an empty string since it’s not possible to rearrange.
  4. Result String: Form the result string by ensuring no two same characters are adjacent.

Code

Here is the Python solution to the problem:

from collections import Counter
import heapq

def reorganizeString(s: str) -> str:
    # Count frequency of each character
    frequency = Counter(s)
    # Create a max heap with negative frequencies (heapq is min heap by default in Python)
    max_heap = [(-count, char) for char, count in frequency.items()]
    heapq.heapify(max_heap)
    
    previous_char, previous_count = None, 0
    result = []
    
    while max_heap:
        count, char = heapq.heappop(max_heap)
        # Add the previous character back if it has remaining count
        if previous_char and previous_count < 0:
            heapq.heappush(max_heap, (previous_count, previous_char))
        
        # Append current character to result
        result.append(char)
        previous_char = char
        previous_count = count + 1  # Decrement the frequency count since it's negative
    
    # Join list to form the final string
    result = ''.join(result)
    
    # Check if the rearrangement is valid
    for i in range(1, len(result)):
        if result[i] == result[i - 1]:
            return ""
    
    return result

# Example usage
s1 = "aab"
s2 = "aaab"
print(reorganizeString(s1))  # Output: "aba"
print(reorganizeString(s2))  # Output: ""

Time Complexity

This solution ensures that we can reorganize the string such that no two adjacent characters are the same, or determine that it is not possible.

Try our interview co-pilot at AlgoAdvance.com