Given a lowercase English string s, rearrange every character so neighboring positions contain different characters. Return any valid rearrangement. Return an empty string when no valid rearrangement exists.
Example 1
Input: s = "aab"
Output: "aba"
Explanation: Both copies of 'a' receive 'b' as a separator. Other valid answers are also accepted.
Example 2
Input: s = "aaab"
Output: ""
Explanation: Three copies of 'a' need two separator positions, but only one different character is available.
Brute Force Approach
The most direct idea tries every possible character order. A partial string grows one position at a time, and any character equal to the last placed character is skipped immediately.
Frequency counts avoid duplicate branches for repeated letters. Backtracking restores every used count, so another possible order can reuse the same character later.
Algorithm
Begin with a frequency array because equal letters share one branch choice instead of producing duplicate permutations.
Keep a growing string and a remaining-position count so every recursive state records the exact unfinished arrangement.
Try every lowercase letter with a positive count because each available letter can occupy the next position.
Skip a letter matching the last placed letter because such a choice breaks the adjacency rule immediately.
Decrease the chosen count and append the letter so the recursive call explores one smaller arrangement.
Restore the count and remove the letter after a failed branch so later branches receive the original state.
Return the first complete string because an exhausted search proves no valid arrangement exists.
Dry Run
Reorganize String Brute
Solution
#include <bits/stdc++.h>using namespace std;class Solution {private: // Builds the first valid complete arrangement bool build(vector<int>& frequency, int remaining, string& current) { // No remaining letter means a valid answer exists if (remaining == 0) { return true; } // Try every available lowercase letter for (int index = 0; index < 26; index++) { // Missing letters cannot fill the next position if (frequency[index] == 0) { continue; } char letter = char('a' + index); // Equal neighbors would break the required order if (!current.empty() && current.back() == letter) { continue; } // Use one copy for the next position frequency[index]--; current.push_back(letter); // A successful suffix completes the arrangement if (build(frequency, remaining - 1, current)) { return true; } // Restore state for the next branch current.pop_back(); frequency[index]++; } // Exhausted choices prove failure for the prefix return false; }public: // Returns an arrangement without equal neighbors string reorganizeString(string s) { // Count every lowercase letter vector<int> frequency(26, 0); for (char letter : s) { frequency[letter - 'a']++; } string current = ""; // A failed search means no arrangement exists if (!build(frequency, s.size(), current)) { return ""; } return current; }};// Driver codeint main() { string s = "aab"; Solution obj; cout << obj.reorganizeString(s) << endl; return 0;}Note: Direct recursion may fail for large input values because it explores an exponential number of different choices or arrangements, so an online judge may report Time Limit Exceeded.
Complexity Analysis
Time Complexity: O(N × N!), where N is the total number of characters, because up to N! arrangements may be explored and forming each complete arrangement can take O(N) time.
Space Complexity: O(N + K), where K is the number of distinct characters. The recursion stack and current arrangement use O(N) space, while the frequency map stores counts for K distinct characters.
Better Approach
Backtracking spends time on many doomed orders. A max heap keeps the most frequent available character at the front, so difficult high-frequency letters receive separators early.
The last placed character stays outside the heap for one turn. A different character must appear before the held character can return, so equal neighbors never form.
Algorithm
Begin with character frequencies because remaining counts determine the safest next choice at every position.
Store all positive counts in a max heap so the largest remaining frequency can be removed quickly.
Keep the previously placed character outside the heap for one turn because immediate reuse would create equal neighbors.
Remove the heap maximum, append the matching character, and decrease the count because one copy has entered the answer.
Reinsert the older held character when a positive count remains because one different character now provides a safe separator.
Hold the newly placed character for the next turn so the same adjacency protection continues across the full string.
Return the built string only when the length equals
nbecause a shorter result leaves an unplaceable held character.
Dry Run
reorganize-string-better-approach
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Returns an arrangement without equal neighbors string reorganizeString(string s) { // Count every lowercase letter vector<int> frequency(26, 0); for (char letter : s) { frequency[letter - 'a']++; } // Keep the largest remaining count at the top priority_queue<pair<int, char>> maxHeap; for (int index = 0; index < 26; index++) { // Only present letters belong in the heap if (frequency[index] > 0) { char letter = char('a' + index); maxHeap.push({frequency[index], letter}); } } string answer = ""; pair<int, char> previous = {0, '#'}; // Place the safest frequent letter at each step while (!maxHeap.empty()) { pair<int, char> current = maxHeap.top(); maxHeap.pop(); // Consume one copy in the answer answer.push_back(current.second); current.first--; // A separator now makes the older letter safe if (previous.first > 0) { maxHeap.push(previous); } // Hold the latest letter for one turn previous = current; } // A shorter result leaves an unsafe letter unused if (answer.size() != s.size()) { return ""; } return answer; }};// Driver codeint main() { string s = "aaabbc"; Solution obj; cout << obj.reorganizeString(s) << endl; return 0;}Complexity Analysis
Time Complexity: O(N log K), where N is the total number of characters and K is the number of distinct characters, because each character may enter or leave a heap containing at most K entries.
Space Complexity: O(K), because the frequency structure and max-heap store at most K distinct characters, excluding the returned string.
Optimal Approach
The fixed lowercase alphabet allows us to place characters directly without using a heap. The most frequent character is the hardest to separate, so it should be placed first at indices 0, 2, 4, ....
After placing it, fill the remaining characters into the next available even positions. Once all even positions are used, continue from index 1 and fill the odd positions 1, 3, 5, .... The condition maxFrequency <= (N + 1) / 2 ensures that such an arrangement is possible.
Algorithm
Create a frequency array of size
26to count all lowercase letters.Find the character with the maximum frequency.
If
maxFrequency > (N + 1) / 2, return an empty string because a valid rearrangement is impossible.Place all copies of the most frequent character at indices
0, 2, 4, ....Place the remaining characters into the next available even positions.
When all even positions are filled, continue from index
1and fill the remaining odd positions.Return the filled character array as a string because this placement strategy prevents equal characters from becoming adjacent.
Dry Run
reorganize-string-optimal-colors-deepened-logo-removed.png
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Returns an arrangement without equal neighbors string reorganizeString(string s) { // Count every lowercase letter vector<int> frequency(26, 0); for (char letter : s) { frequency[letter - 'a']++; } int maxIndex = 0; // Find the hardest letter to separate for (int index = 1; index < 26; index++) { // A larger count needs wider positions first if (frequency[index] > frequency[maxIndex]) { maxIndex = index; } } int n = s.size(); int limit = (n + 1) / 2; // Excess copies cannot receive enough separators if (frequency[maxIndex] > limit) { return ""; } string answer(n, ' '); int position = 0; // Give the hardest letter every wide slot first while (frequency[maxIndex] > 0) { answer[position] = char('a' + maxIndex); position += 2; frequency[maxIndex]--; } // Fill all remaining letters two positions apart for (int index = 0; index < 26; index++) { while (frequency[index] > 0) { // Exhausted even slots lead to odd slots if (position >= n) { position = 1; } answer[position] = char('a' + index); position += 2; frequency[index]--; } } return answer; }};// Driver codeint main() { string s = "aaabbc"; Solution obj; cout << obj.reorganizeString(s) << endl; return 0;}Complexity Analysis
Time Complexity: O(N + K), where N is the total number of characters and K is the number of distinct possible letters. Frequency counting and result construction process N characters, while finding the maximum scans the K letters.
Space Complexity: O(K), because the frequency array stores one count for each possible letter, excluding the returned string.
Interview follow-up Questions
No. Inputs with several distinct letters can produce many accepted rearrangements. Every accepted result only needs matching character counts and different adjacent characters.
Be the first to add a comment.