Problem

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.

Examples

Example 1:

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

Example 2:

Input: s = "aaab"
Output: ""

Solution

Method 1 - Using MaxHeap and Frequency Hashmap

How can we achieve this rearrangement? The initial idea might be to count the frequency of each character and rearrange them based on the count. However, if more than n/2 characters are the same, rearrangement is impossible because more than n/2 duplicates would require more than n/2 other unique characters to intertwine them.

If no character exceeds n/2 duplicates, rearrangement becomes feasible by placing a different character between two duplicates. However, other characters may also have duplicates. So, how do we choose a character to put it in between two other duplicates?

By determining the frequency of each unique character, we understand that the most frequent character needs to be interleaved by another. The arrangement is straightforward if there are only two unique characters, each appearing n/2 times, as in “aaabbb” becoming “ababab”. But with multiple repeating characters, as long as no character exceeds n/2 repetitions, another character with equal or lower frequency can always be found to interleave.

This leads to the idea of taking the two most frequent characters, interleaving them as much as possible, then moving onto the next two most frequent, and so on. This is similar to Huffman Coding, where the two most frequent characters are merged into a node summing their frequencies. Here, we reduce their frequencies instead of merging them, ensuring we always have two characters with similar frequencies to interleave.

To implement this, maintain a MaxHeap (priority queue) of the character frequency histogram. Extract the two most frequent characters, place them in adjacent positions, then reinsert them into the heap with reduced frequencies. This ensures that no two identical characters are adjacent. The following implementation uses a PriorityQueue to form the max heap.

Here is the approach:

  1. count letter appearance and store in hash[i] OR priority Queye
  2. find the letter with largest occurrence.
  3. put the letter into the index such that they are not adjacent.
  4. put the rest into the array

Code

Java
public class Solution {
    public String reorganizeString(String s) {
        // Calculate frequency of each character
        Map<Character, Integer> freqMap = new HashMap<>();
        int n = s.length();
        
        for (char ch : s.toCharArray()) {
            int count = freqMap.getOrDefault(ch, 0) + 1;
            // If frequency of any character is more than half of the string length, return ""
            if (count > (n + 1) / 2) {
                return "";
            }
            freqMap.put(ch, count);
        }

        // PriorityQueue to store pairs of (character, frequency) sorted by frequency descending
        PriorityQueue<Map.Entry<Character, Integer>> maxHeap = new PriorityQueue<>((a, b) -> b.getValue() - a.getValue());
        maxHeap.addAll(freqMap.entrySet());

        // StringBuilder to construct the result
        StringBuilder res = new StringBuilder();
        while (!maxHeap.isEmpty()) {
            Map.Entry<Character, Integer> first = maxHeap.poll();
            
            // Append the most frequent character
            if (res.length() == 0 || first.getKey() != res.charAt(res.length() - 1)) {
                res.append(first.getKey());
                int newVal = first.getValue() - 1;
                if (newVal > 0) {
                    first.setValue(newVal);
                    maxHeap.offer(first);
                }
            } else {
                Map.Entry<Character, Integer> second = maxHeap.poll();
                res.append(second.getKey());
                int newVal = second.getValue() - 1;
                if (newVal > 0) {
                    second.setValue(newVal);
                    maxHeap.offer(second);
                }
                // Reinsert the first character back into the heap
                maxHeap.offer(first);
            }
        }
        return res.toString();
    }
}
Python
class Solution:
    def reorganizeString(self, s: str) -> str:
        # Calculate frequency of each character
        freq_map = Counter(s)
        n = len(s)
        
        for count in freq_map.values():
            if count > (n + 1) // 2:
                return ""
        
        # Create a max-heap (priority queue)
        max_heap = [(-cnt, char) for char, cnt in freq_map.items()]
        heapq.heapify(max_heap)

        # List to construct the result
        res = []
        prev_count, prev_char = 0, ''

        while max_heap:
            count, char = heapq.heappop(max_heap)
            res.append(char)

            # If previous character can still be used, push it back into the heap
            if prev_count < 0:
                heapq.heappush(max_heap, (prev_count, prev_char))

            # Update the previous character and frequency to use next time
            prev_count, prev_char = count + 1, char

        # If the rearranged string's length is not equal to the input string's length
        # then it means rearrangement is not possible
        rearranged_string = ''.join(res)
        return rearranged_string if len(rearranged_string) == len(s) else ""

Complexity

  • ⏰ Time complexity: O(n log n)
    • Frequency Calculation: Iterating through the string to count character frequencies takes O(n).
    • Building the Max-Heap: Inserting each character into the max-heap takes O(n log n) because there are up to n insertions, each taking O(log n).
    • Constructing the Result: Extracting elements from the heap to build the result string also takes O(n log n) since we extract and potentially re-insert up to n elements.
  • 🧺 Space complexity: O(n)
    • Frequency Map: Storing character frequencies requires O(n) space in the worst case (each character is unique).
    • Max-Heap: The max-heap may contain up to n elements, each requiring space proportional to the number of characters, resulting in O(n).
    • Result Storage: Constructing the result string in a string builder or list requires O(n) space.

Method 2 - Using custom class and char array as map

This is similar to previous code, just with custom class CharFreq and charr array as frequency map.

Code

Java
public class Solution {
    public static String reorganizeString(String str) {
        final class CharFreq implements Comparable<CharFreq> {
            char c;
            int freq;

            public CharFreq(char ch, int count) {
                c = ch;
                freq = count;
            }

            @Override
            public int compareTo(CharFreq o) {
                int comp = Integer.compare(o.freq, freq); // Compare frequencies in descending order
                if (comp == 0) {
                    comp = Character.compare(c, o.c);
                }
                return comp;
            }
        }

        int n = str.length();
        StringBuilder rearranged = new StringBuilder();
        PriorityQueue<CharFreq> maxHeap = new PriorityQueue<>();
        int[] freqHistogram = new int[256];

        // Build the character frequency histogram
        for (char c : str.toCharArray()) {
            freqHistogram[c]++;

            // If a character repeats more than (n+1)/2 times, it's not possible to rearrange
            if (freqHistogram[c] > (n + 1) / 2) {
                return "";
            }
        }

        // Build the max heap from the histogram
        for (int i = 0; i < 256; i++) {
            if (freqHistogram[i] > 0) {
                maxHeap.add(new CharFreq((char) i, freqHistogram[i]));
            }
        }

        // Rearrange by popping the top 2 most frequent items and arranging them in adjacent positions
        while (!maxHeap.isEmpty()) {
            // Extract the most frequent character
            CharFreq first = maxHeap.poll();
            rearranged.append(first.c);
            first.freq--;

            CharFreq second = null;
            // Extract the next most frequent character
            if (!maxHeap.isEmpty()) {
                second = maxHeap.poll();
                rearranged.append(second.c);
                second.freq--;
            }

            // Add the updated frequencies back to the heap
            if (first.freq > 0) {
                maxHeap.add(first);
            }
            if (second != null && second.freq > 0) {
                maxHeap.add(second);
            }
        }

        return rearranged.toString();
    }
}
Python
class Solution:
    def reorganizeString(self, s: str) -> str:
        class CharFreq:
            def __init__(self, ch: str, count: int):
                self.c = ch
                self.freq = count
                
            def __lt__(self, other):
                # We compare frequencies in reverse order to build a max-heap
                return self.freq < other.freq

        n = len(s)
        freq_map = Counter(s)
        
        # If a character repeats more than (n+1)/2 times, it's not possible to rearrange
        if any(count > (n + 1) // 2 for count in freq_map.values()):
            return ""

        # Build the max-heap from the histogram
        max_heap = [CharFreq(c, freq) for c, freq in freq_map.items()]
        heapq.heapify(max_heap)
        
        res = []
        
        # Rearrange by popping the top 2 most frequent items and arranging them in adjacent positions
        while max_heap:
            first = heapq.heappop(max_heap)
            res.append(first.c)
            first.freq -= 1
            
            if max_heap:
                second = heapq.heappop(max_heap)
                res.append(second.c)
                second.freq -= 1
                
                if second.freq > 0:
                    heapq.heappush(max_heap, second)
            
            if first.freq > 0:
                heapq.heappush(max_heap, first)
        
        return "".join(res)

Complexity

  • ⏰ Time complexity: O(n log n)
  • 🧺 Space complexity: O(n)