Skip to main content

Heaps

Reorganize String Solution In C++/Java/Python/Javascript

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.

Examples

Input: s = "aab"
Output: "aba"
Explanation: In the rearranged string "aba", no two adjacent characters are the same.
The first 'a' is followed by 'b'.
The 'b' is followed by another 'a'.

Input: s = "aaab"
Output: ""
Explanation: In the rearranged string "aaba", two adjacent characters are the same so return "" as no possible rearrangement of s .

Constraints

  • 1 <= s.length <= 500
  • s consists of lowercase English letters.
💡
Try it Yourself First
Since we need to rearrange characters to avoid adjacent duplicates, we first check their frequencies. If any appear too often, it's impossible. Using a max heap, we place the most frequent ones first to ensure valid spacing.

Brute Force Approach

Intuition

Our goal is to rearrange the characters of the string so that no two adjacent characters are the same. But here's the challenge - Some characters may occur more frequently than others, so we need to thoughtfully arrange them to ensure the condition is satisfied and no two adjacent characters are the same.

To tackle this, we start by analyzing the frequency of each character. Why? Because the more frequently a character appears, the trickier it is to place it without causing adjacency issues. Imagine trying to juggle a string like "aaaabb"-clearly, those three 'a's will need careful placement.

Once we know the frequency of each character, the idea is simple: start placing the most frequent characters first. Why prioritize them? Because they have the highest chance of creating conflicts if left to the end. Using a greedy approach, we keep track of which character was just placed (so we don't repeat it immediately) and ensure the remaining characters are placed in a way that avoids adjacency violations.

So ,it involves analyzing the string's character frequencies, focusing on the most frequent ones to strategically place them, and gradually constructing the output string to avoid adjacent duplicates. It's similar to solving a puzzle by placing the largest and most challenging pieces first to create a stable foundation.

Approach

Step 1: Character Frequency Analysis & Validation
The first step in this approach is to calculate the frequency of each character in the input string. We use a vector of size 26 to count how many times each character appears.
While counting, we also perform an early validation check:

  • if any character appears more than (n+1)/2 times, where n is the length of the string, it's impossible to rearrange the string to satisfy the "no adjacent duplicates" condition. This allows us to immediately return an empty string in such cases without further processing.

Step 2: Max Heap Construction
After validating the input, we move to building a max heap (priority queue) that stores pairs of (frequency,character). This heap helps us always access the character with the highest frequency efficiently. By utilizing this structure, we ensure that we can always extract the most frequent character available and place it into the result string, ensuring a greedy approach to solve the problem.

Step 3: String Construction with Greedy Placement
This is the key phase, where we construct the result string. At each step:

  • Extract the character with the highest frequency from the heap.
  • Add this character to the result string.
  • Decrease the character's frequency by one and, if it still has remaining occurrences, reinsert it into the heap.
  • We ensure that the previous character isn't placed consecutively, so we track the previous character and push it back into the heap only when necessary.
    If at any point the heap is empty but there are still characters to place, we return an empty string, indicating that rearrangement is impossible.

Dry Run

Input: s = "aab"
Step 1: Count the Frequency of Each Character
Iterate through the string and count how many times each character appears. Use a frequency array frequency of size 26 (for 'a' to 'z').
For s = "aab":
a -> seen 2 times
b -> seen 1 time
Frequency array: [2, 1, 0, 0, ..., 0]
Important Check:
If any character's frequency exceeds (n + 1) / 2, reorganization is impossible.
Here, (n + 1) / 2 = (3 + 1) / 2 = 2.
Max frequency is 2 (a), so it's valid to proceed.
Step 2: Create a Max Heap
Use a max heap (priority queue) to store pairs {frequency, character}. This helps prioritize placing characters with higher frequencies first.
From the frequency array:
Push {2, 'a'} and {1, 'b'} into the heap.
Heap state:
Initially: {(2, 'a'), (1, 'b')}
Step 3: Build the Reorganized String
Use a greedy approach to construct the string:
Extract the character with the highest frequency.
Append it to the result.
Reduce its frequency and track it as the "previous character" to avoid adjacent repetitions.
If the previous character still has a positive frequency, push it back into the heap.
Iteration 1:
Extract (2, 'a') from the heap.
Append 'a' to the result.
Frequency of 'a' becomes 1.
Push (1, 'b') back into the heap.
Result so far: "a"
Iteration 2:
Extract (1, 'b') from the heap.
Append 'b' to the result.
Frequency of 'b' becomes 0.
Push (1, 'a') (previous character) back into the heap.
Result so far: "ab"
Iteration 3:
Extract (1, 'a') from the heap.
Append 'a' to the result.
Frequency of 'a' becomes 0.
Heap is now empty.
Result so far: "aba"
Step 4: Final Output
The heap is empty, and the result string is built successfully without adjacent characters being the same.
Output: "aba"
Why This Works:
Frequency Tracking: Ensures we prioritize the most frequent characters, which need strategic placement to avoid adjacency.
Max Heap: Provides an efficient way to always access the character with the highest remaining frequency.
Greedy Approach: Guarantees no adjacent characters are the same by deferring and re-adding characters with leftover frequencies.
This approach efficiently builds the string with the desired properties.

Code for All Languages
C++ 
// Approach: Reorganize String using brute force approach
// Language: C++
// This program rearranges characters of a string such that no two adjacent characters are the same.
// It uses a max heap (priority queue) to manage character frequencies for greedy placement.

class Solution {
public:
    // Function to reorganize the string
    // Time Complexity: O(n log k), where n is the length of the string and k is the number of unique characters
    // Space Complexity: O(k)
    string reorganizeString(string s) {
        // Step 1: Count the frequency of each character
        vector<int> frequency(26, 0);

        // Populate the frequency array and check for impossible cases
        for (char c : s) {
            frequency[c - 'a']++;

            // If any character appears more than (n + 1) / 2 times, reorganization is impossible
            if (frequency[c - 'a'] > (s.length() + 1) / 2) {
                return "";
            }
        }

        // Step 2: Create a max heap to store {frequency, character} pairs
        priority_queue<pair<int, char>> max_heap;

        // Add characters with their frequencies to the heap
        for (char c = 'a'; c <= 'z'; ++c) {
            if (frequency[c - 'a'] > 0) {
                max_heap.push({frequency[c - 'a'], c});
            }
        }

        // Step 3: Build the reorganized string
        string result = "";
        pair<int, char> prev = {0, '#'}; // To track the previous character and its remaining frequency

        while (!max_heap.empty() || prev.first > 0) {
            // If the heap is empty but a character is still left, reorganization is impossible
            if (max_heap.empty() && prev.first > 0) {
                return "";
            }

            // Extract the character with the highest frequency
            auto curr = max_heap.top();
            max_heap.pop();

            // Add the character to the result and decrease its frequency
            result += curr.second;
            curr.first--;

            // If the previous character still has a frequency left, push it back into the heap
            if (prev.first > 0) {
                max_heap.push(prev);
            }

            // Update prev to the current character
            prev = curr;
        }
        return result;
    }
};

Java 
// Approach: Reorganize String using the brute force approach
// Language: Java

class Solution {
    // Function to reorganize the string
    // Time: O(n log k), where n is the length of the string and k is the number of unique characters
    // Space: O(k)
    public String reorganizeString(String s) {
        // Step 1: Count the frequency of each character using a HashMap
        Map<Character, Integer> frequency = new HashMap<>();

        for (char c : s.toCharArray()) {
            frequency.put(c, frequency.getOrDefault(c, 0) + 1);

            // If any character appears more than (n + 1) / 2 times, reorganization is impossible
            if (frequency.get(c) > (s.length() + 1) / 2) {
                return "";
            }
        }

        // Step 2: Use a max heap (priority queue) to store characters by their frequency
        PriorityQueue<Map.Entry<Character, Integer>> maxHeap = new PriorityQueue<>(
            (a, b) -> b.getValue() - a.getValue()
        );
        maxHeap.addAll(frequency.entrySet());

        // Step 3: Build the reorganized string
        StringBuilder result = new StringBuilder();
        Map.Entry<Character, Integer> prev = null; // To track the previous character and its remaining frequency

        while (!maxHeap.isEmpty() || (prev != null && prev.getValue() > 0)) {
            // If the heap is empty but a character is still left, reorganization is impossible
            if (maxHeap.isEmpty() && prev != null && prev.getValue() > 0) {
                return "";
            }

            // Extract the character with the highest frequency
            Map.Entry<Character, Integer> curr = maxHeap.poll();

            // Add the character to the result and decrease its frequency
            result.append(curr.getKey());
            curr.setValue(curr.getValue() - 1);

            // If the previous character still has a frequency left, push it back into the heap
            if (prev != null && prev.getValue() > 0) {
                maxHeap.add(prev);
            }

            // Update prev to the current character
            prev = curr;
        }

        return result.toString();
    }
}

Python 
# Approach: Reorganize String using a max heap to avoid adjacent repeating characters
# Language: Python

class Solution:
    # Function to reorganize the string
    # Time Complexity: O(n log k), where n is the length of the string and k is the number of unique characters
    # Space Complexity: O(k)
    def reorganizeString(self, s):
        # Step 1: Count the frequency of each character
        freq = Counter(s)

        # Step 2: Check if reorganization is possible
        if any(f > (len(s) + 1) // 2 for f in freq.values()):
            return ""

        # Step 3: Use a max heap (priority queue) to store characters by their frequency
        max_heap = [(-f, c) for c, f in freq.items()]
        heapq.heapify(max_heap)

        # Step 4: Build the reorganized string
        result = []
        prev_freq, prev_char = 0, ''  # Track the previous character and its remaining frequency

        while max_heap or prev_freq < 0:
            # If the heap is empty but a character is still left, return empty
            if not max_heap and prev_freq < 0:
                return ""

            # Extract the character with the highest frequency
            curr_freq, curr_char = heapq.heappop(max_heap)
            result.append(curr_char)

            # Decrease its frequency
            curr_freq += 1  

            # Push the previous character back into the heap if it still has remaining frequency
            if prev_freq < 0:
                heapq.heappush(max_heap, (prev_freq, prev_char))

            # Update previous character to the current one
            prev_freq, prev_char = curr_freq, curr_char

        return ''.join(result)

Javascript 
// Approach: Reorganize String using Brute Force + Max Heap
// Language: JavaScript

/**
 * @param {string} s
 * @return {string}
 */
var reorganizeString = function(s) {
    // Function to reorganize the string
    // Time Complexity: O(n log k), where n is the length of the string and k is the number of unique characters
    // Space Complexity: O(k)
    // Step 1: Count frequency of characters using a HashMap
    let freqMap = new Map();
    for (let char of s) {
        freqMap.set(char, (freqMap.get(char) || 0) + 1);

        // If any character appears more than (n + 1) / 2 times, reorganization is impossible
        if (freqMap.get(char) > Math.floor((s.length + 1) / 2)) {
            return "";
        }
    }

    // Step 2: Use a max heap (priority queue) to store characters by frequency
    let maxHeap = Array.from(freqMap.entries()).sort((a, b) => b[1] - a[1]);

    // Step 3: Build the reorganized string
    let result = [];
    // Store previous character and its remaining count
    let prev = [null, 0]; 

    while (maxHeap.length || prev[1] > 0) {
        // If heap is empty but a character is still left, reorganization is impossible
        if (!maxHeap.length && prev[1] > 0) {
            return "";
        }

        // Extract the character with the highest frequency
        let [currChar, currFreq] = maxHeap.shift();
        result.push(currChar);
        currFreq--;

        // Push the previous character back into heap if it still has remaining frequency
        if (prev[1] > 0) {
            maxHeap.push(prev);
            // Maintain max heap order
            maxHeap.sort((a, b) => b[1] - a[1]); 
        }

        // Update previous character
        prev = [currChar, currFreq];
    }

     // Return the reorganized string
    return result.join("");
};

Time Complexity : O( nlogk )

  1. Frequency Analysis & Validation
  • String Traversal: We iterate through the string once to count the frequencies, which is O(n) where n is the length of the string.
  • Frequency Counting: For each character, counting its frequency is O(1).
  • Validation: Checking if the frequency exceeds (n+1)/2 is also O(1) for each character.
  • Total for this phase: O(n).
  1. Heap Operations :
  • Heap Construction: We need to push at most k unique characters (where k is the number of unique characters in the string). This takes O(klogk) time.
  • Character Placement: For each character in the result string (up to n characters), we perform a heap operation (extract and insert), which takes O(logk).
  • Total heap operations: O(nlogk).
  • Overall Time Complexity: The time complexity is dominated by the heap operations, so the final time complexity is O(nlogk), where n is the length of the string and k is the number of unique characters.

Space Complexity : O(k+n)

  • Frequency Vector: The frequency array has a fixed size of 26, so the space complexity is O(1).
  • Max Heap: The max heap can store at most k unique characters, so the space complexity is O(k).
  • Output String: The space needed to store the output string is O(n), where n is the length of the string.
  • Auxiliary Space Complexity: The auxiliary space complexity (excluding the space required for the output string) is O(k).
  • The total space complexity is O(k+n), accounting for both the heap and the output string.
So now, we’re thinking smarter: Instead of relying on a heap for extra overhead, we simply count the frequencies and directly place the characters in the result string. By alternating between even and odd indices, we efficiently manage the placement without the need for complex data structures, streamlining the process while still achieving the desired result.

Optimal Approach

Intuition

Let’s aim for a smarter way to rearrange the string. The idea here is to focus on efficiency and structure. The first question we ask is: what’s the most frequent character in the string? Why? Because if any character’s frequency exceeds half the string length (rounded up), it’s impossible to rearrange the string without adjacent duplicates. This gives us an early exit if the condition isn’t met.

Now, assuming reorganization is possible, the optimal way forward is to place the most frequent character at even indices first. Why? This ensures that the most frequent character gets evenly distributed across the string, significantly reducing the risk of adjacency conflicts.

Once the most frequent character is placed, we fill in the remaining slots with the other characters. Starting with even indices (if available) and moving to odd indices ensures that every character finds a place without violating the adjacency rule. This method not only minimizes the risk of conflicts but also guarantees that the string is built in a straightforward and efficient manner.

In essence, this approach cleverly combines frequency analysis with strategic placement to achieve the goal while avoiding unnecessary complexity. It’s all about placing the “troublemakers” (frequent characters) first and letting the rest fall into place naturally.

Approach

Step 1: Character Frequency Calculation
The first step involves calculating the frequency of each character in the input string. We use a vector of size 26 (for each lowercase letter) to store the frequency count of each character. This gives us a count of how many times each character appears in the string.

Step 2: Identifying the Most Frequent Character
After counting the frequencies, we identify the character with the highest frequency. This is crucial because, if the most frequent character appears more than (n+1)/2 times (where n is the length of the string), it's impossible to rearrange the string such that no two adjacent characters are the same. If the condition is violated, we immediately return an empty string.

Step 3: Reorganization Feasibility Check
In this step, we check if the reorganization is possible by comparing the frequency of the most frequent character with the threshold value (n+1)/2. If the most frequent character exceeds this threshold, we know that the string cannot be reorganized and we return an empty string.

Step 4: Placing the Most Frequent Character
If the reorganization is possible, we begin placing the most frequent character at even indices (0, 2, 4, …) in the result array. This helps ensure that the most frequent character doesn't appear next to itself. We reduce its frequency after each placement.

Step 5: Filling in the Remaining Characters
Once the most frequent character is placed, we move on to placing the remaining characters. For each character, we place it in the next available position, starting from index 1 (odd indices), if even indices are filled. This ensures that characters are placed in such a way that no two adjacent characters are the same.

Dry Run

Input: s = "aab"
Step 1: Count the Frequency of Each Character
Iterate through the string to count how many times each character appears. Store the counts in a frequency array of size 26 (for 'a' to 'z').
For s = "aab":
a -> seen 2 times
b -> seen 1 time
Frequency array: [2, 1, 0, 0, ..., 0]
Step 2: Identify the Most Frequent Character
Scan the frequency array to find the character with the highest frequency.
For the frequency array:
Maximum frequency = 2 (character 'a' with index 0).
Most frequent character: 'a' with frequency 2.
Step 3: Check Reorganization Possibility
If the maximum frequency is greater than (n + 1) / 2, reorganization is impossible.
Here, (n + 1) / 2 = (3 + 1) / 2 = 2.
Since the maximum frequency is 2, it's possible to reorganize the string.
Step 4: Place the Most Frequent Character at Even Indices
Start placing the most frequent character 'a' at even indices (0, 2, ...).
This ensures the most frequent character doesn’t end up adjacent to itself.
Result array after placing 'a':
['a', ' ', 'a']
Step 5: Place the Remaining Characters
Fill the remaining characters in the result array:
Start from even indices if available.
Switch to odd indices if even indices are full.
For s = "aab":
Place 'b' at index 1 (next available odd index).
Result array after placing all characters:
['a', 'b', 'a']
Final Output
Convert the result array back to a string and return it.
Output: "aba"

Why This Works:
Frequency Check: Ensures it's possible to reorganize the string without adjacent characters being the same.
Greedy Placement: Placing the most frequent character first at even indices avoids adjacency issues early on.
Efficient Filling: Remaining characters are added to available indices without violating adjacency rules.

Code for All Languages
C++ 
// Approach: Reorganize String to Avoid Adjacent Repeating Characters
// Language: C++

class Solution {
public:
    // Function to reorganize a string so that no adjacent characters are the same
    // Time: O(n), where n is the length of the string
    // Space: O(n) for the result string and character frequency tracking
    string reorganizeString(string s) {
        // Step 1: Count the frequency of each character
        vector<int> frequency(26, 0);
        for (char c : s) {
            frequency[c - 'a']++;
        }

        // Step 2: Identify the character with the maximum frequency
        int maxFrequency = 0, maxCharIndex = 0;
        for (int i = 0; i < 26; i++) {
            if (frequency[i] > maxFrequency) {
                maxFrequency = frequency[i];
                maxCharIndex = i;
            }
        }

        // Step 3: Check if reorganization is possible
        if (maxFrequency > (s.length() + 1) / 2) {
            return "";
        }

        // Step 4: Place the most frequent character at even indices
        vector<char> result(s.length(), ' ');
        int index = 0;
        while (frequency[maxCharIndex]-- > 0) {
            result[index] = maxCharIndex + 'a';
            index += 2;
        }

        // Step 5: Place the remaining characters
        for (int i = 0; i < 26; i++) {
            while (frequency[i]-- > 0) {
                if (index >= s.length()) {
                    index = 1;
                }
                result[index] = i + 'a';
                index += 2;
            }
        }
        return string(result.begin(), result.end());
    }
};

Java 
// Approach: Reorganize String to Avoid Adjacent Repeating Characters
// Language: Java

class Solution {
    // Function to reorganize a string so that no adjacent characters are the same
    // Time Complexity: O(n), where n is the length of the string
    // Space Complexity: O(n) for result string and character frequency tracking

    public String reorganizeString(String s) {
        // Step 1: Count the frequency of each character
        int[] freq = new int[26];
        for (char c : s.toCharArray()) {
            freq[c - 'a']++;
        }

        // Step 2: Identify the character with the maximum frequency
        int maxFreq = 0, maxChar = 0;
        for (int i = 0; i < 26; i++) {
            if (freq[i] > maxFreq) {
                maxFreq = freq[i];
                maxChar = i;
            }
        }

        // Step 3: Check if reorganization is possible
        // If the most frequent character appears more than (n + 1) / 2 times, return an empty string
        if (maxFreq > (s.length() + 1) / 2) return "";

        // Step 4: Place the most frequent character at even indices first
        char[] result = new char[s.length()];
        int idx = 0;
        while (freq[maxChar]-- > 0) {
            result[idx] = (char) (maxChar + 'a');
            idx += 2;
        }

        // Step 5: Place the remaining characters in the empty positions
        for (int i = 0; i < 26; i++) {
            while (freq[i]-- > 0) {
                if (idx >= s.length()) idx = 1; // Move to odd indices if even indices are filled
                result[idx] = (char) (i + 'a');
                idx += 2;
            }
        }

        // Return the reorganized string
        return new String(result);
    }
}

Python 
# Approach: Reorganize String to Avoid Adjacent Repeating Characters
# Language: Python

class Solution(object):
    def reorganizeString(self, s):
        """
        :type s: str
        :rtype: str
        """
        """
        Function to reorganize a string so that no adjacent characters are the same
        Time Complexity: O(n log k), where n is the length of the string and k is the number of unique characters
        Space Complexity: O(n) for result string and character frequency tracking
        """
        # Step 1: Count the frequency of each character
        freq = Counter(s)

        # Step 2: Identify the character with the maximum frequency
        max_freq = max(freq.values())

        # Step 3: Check if reorganization is possible
        if max_freq > (len(s) + 1) // 2:
            return ""

        # Step 4: Use a max heap (priority queue) to store characters by their frequency
        max_heap = [(-count, char) for char, count in freq.items()]
        heapq.heapify(max_heap)

        # Step 5: Build the reorganized string
        result = []
        # To track the previous character and its count
        prev = (0, '')  

        while max_heap:
            # Extract the most frequent character
            count, char = heapq.heappop(max_heap) 
            result.append(char)
            # Decrease frequency
            count += 1  

            # Push the previous character back if it still has remaining count
            if prev[0] < 0:
                heapq.heappush(max_heap, prev)
            # Update previous character
            prev = (count, char)  

        return "".join(result)

Javascript 
// Approach: Reorganize String using Greedy + Max Heap
// Language: JavaScript

/**
 * @param {string} s
 * @return {string}
 */
var reorganizeString = function(s) {
    //  Function to reorganize the string
    //  Time: O(n log k), where n is the length of the string and k is the number of unique characters
    //  Space: O(k)
    // Step 1: Count frequency of each character
    let freq = new Array(26).fill(0);
    for (let char of s) {
        freq[char.charCodeAt(0) - 'a'.charCodeAt(0)]++;
    }

    // Step 2: Find the most frequent character
    let maxFreq = 0, maxChar = 0;
    for (let i = 0; i < 26; i++) {
        if (freq[i] > maxFreq) {
            maxFreq = freq[i];
            maxChar = i;
        }
    }

    // Step 3: Check if reorganization is possible
    if (maxFreq > Math.floor((s.length + 1) / 2)) return "";

    // Step 4: Place the most frequent character at even indices
    let result = new Array(s.length);
    let index = 0;
    while (freq[maxChar]-- > 0) {
        result[index] = String.fromCharCode(maxChar + 'a'.charCodeAt(0));
        index += 2;
    }

    // Step 5: Place remaining characters
    for (let i = 0; i < 26; i++) {
        while (freq[i]-- > 0) {
            // Switch to odd index if even slots are full
            if (index >= s.length) index = 1; 
            result[index] = String.fromCharCode(i + 'a'.charCodeAt(0));
            index += 2;
        }
    }

    // Return the reorganized string
    return result.join(""); 
};

Time Complexity : O( n )

  • For String Traversal: We traverse the input string once to count the frequency of each character, which takes O(n), where n is the length of the string.
  • Finding Maximum Frequency: We loop over the frequency array (size 26), which takes O(26), but this is effectively constant time, O(1), as the size is fixed. 
  • Placing the Character: We place the most frequent character at even indices. The number of times we place this character is equal to its frequency, so this step takes O(n) in the worst case. Total for this phase: O(n).
  • Placing Remaining Characters: For each of the remaining characters, we place them one by one. This can take up to O(n), as there are n positions to fill. 
  • Overall Time Complexity:
    The overall time complexity is dominated by the string traversal and placement steps, so the final time complexity is O(n), where n is the length of the string.

Space Complexity : O(n)

  • Frequency Array: The frequency array has a fixed size of 26 (for each lowercase letter), so it requires O(1) space.
  • Result String: The result string stores the reorganized characters, which takes O(n) space, where n is the length of the string.
    Total Space Complexity:
  • The overall space complexity is O(n), due to the storage required for the result string. The auxiliary space complexity is O(1) since the frequency array and other variables use constant space.

Learning Tip

Now we have successfully tackled this problem, let’s try these similar problems.

Task Scheduler

Given tasks labeled A-Z and a cooldown n, find the minimum time to complete all tasks, ensuring the same task appears only after n intervals.

Longest Happy String

Construct the longest string using 'a', 'b', and 'c' without "aaa", "bbb", or "ccc", while keeping counts within given limits for each letter.