Given a string S, rearrange the characters in a string S so that no two adjacent characters are the same. Return any possible rearrangement of s, an empty string “” if none is possible.

Examples:

Input: aadbc

Output: abadc

Input: aaabc

Output: abaca

Input: aaba

Output: “”

Input: aaaaabc

Output: “”

Before moving to the solution, we recommend you to try this problem by yourself: Rearrange String.

Connect with our expert counsellors to understand how to hack your way to success

User rating 4.7/5

1:1 doubt support

95% placement record

Akash Pal

Senior Software Engineer

326% Hike After Job Bootcamp

Himanshu Gusain

Programmer Analyst

32 LPA After Job Bootcamp

After Job Bootcamp

Approach - Using Max Heap

For a better understanding of this approach, you should know about the priority queue.

First, we will count the number of times each character appears in the given string.

We will return an empty string if any character’s frequency exceeds the half-length of the string because in this case, no valid character rearrangement can be done.

For example, aaaaabb, aaaaaabc, in these two strings character ‘a’ occurs more than half of the string length, so no valid character rearrangement can be done.

Now, we create a max_heap from the frequency of characters. Here, we use a pair for the character’s count, pair<countOfChar, char>.

This is the major part of the entire algorithm.

int i = 0; We are storing rearrangement from the first index, obviously, in the input string itself.

pair<int, char> prev = max_heap.top(); max_heap.pop(); Create a pair to store the first top pair of max_heap

s[i++] = prev.second;

Store the character into the input string itself from index 0.

Now pop another pair from max_heap and put the character from the pair into the input string, reduce the charCount in the prev pair, and push the pair back to max_heap if more occurrences of character remain.

Repeat this procedure until max_heap is empty.

while (!max_heap.empty()) {
pair<int, char> curr = max_heap.top();
max_heap.pop();
s[i++] = curr.second;
if (--prev.first) max_heap.push(prev);
prev = curr;
}

Code in C++

#include<bits/stdc++.h>
using namespace std;
string rearrangeString(string s) {
vector<int> freq(26);
for (int i = 0; i < s.length(); i++) {
freq[s[i] - 'a']++;
if (freq[s[i] - 'a'] > (s.length() + 1) / 2)
return "";
}
priority_queue<pair<int, char>> max_heap;
for (int i = 0; i < 26; i++) {
if (freq[i]) {
max_heap.push({freq[i], 'a' + i});
}
}
int i = 0;
pair<int, char> prev = max_heap.top();
max_heap.pop();
s[i++] = prev.second;
while (! max_heap.empty()) {
pair<int, char> curr = max_heap.top();
max_heap.pop();
s[i++] = curr.second;
if (--prev.first)
max_heap.push(prev);
prev = curr;
}
return s;
}
int main()
{
string s;
cin >> s;
cout << rearrangeString(s) << endl;
}

Input1

aadbc

Output1

adcba

Input2

aaabc

Output2

acaba

Complexity Analysis

Time complexity- If n is the given string’s length, the solution’s time complexity is O(n log n).

Space complexity- The space complexity of the above solution is O(n) because the priority queue at max can contain the whole string.

Check if the frequency of the most frequent character is more than the half-length of the given string. If yes, return an empty string because, in this case, we cannot rearrange the string as per the required condition.

Start filling the most frequent character at alternate places starting from the index 0(even indexes), eg: 0,2,4,6 .....

Start filling the other characters with a gap of 1 index, from where the most frequent element got exhausted(continue for even indexes).

If we reach the end of the string size in this process, then start filling for odd indexes starting from 1 and continue with a gap of 1, e.g. 1,3,5,7.....

Code in C++

#include<bits/stdc++.h>
using namespace std;
string rearrangeString(string S) {
vector<int> freq(26);
int mostFreq = 0, i = 0;
for (int i = 0; i < S.length(); i++)
{ freq[S[i] - 'a']++;
if (freq[S[i] - 'a'] > freq[mostFreq])
mostFreq = (S[i] - 'a');
}
if (freq[mostFreq] > (S.length() + 1) / 2) return "";
while (freq[mostFreq]) {
S[i] = ('a' + mostFreq);
i = i + 2;
freq[mostFreq]--;
}
for (int j = 0; j < 26; j++) {
while (freq[j]) {
if (i >= S.length())
i = 1;
S[i] = ('a' + j);
freq[j]--;
i = i + 2;
}
}
return S;
}
int main()
{
string s;
cin >> s;
cout << rearrangeString(s) << endl;
}

Input1

aadbc

Output1

acadb

Input2

aaabc

Output2

abaca

Complexity Analysis

Time complexity- It is O(n), where n is the length of the given string.

Space complexity - It is O(26) because we are using a vector of size 26 for storing the frequency of the characters.

The priority queue is an extension of the "normal" queue. It's an abstract data type that holds a collection of items. It's similar to a "normal" queue, except the dequeuing elements are prioritized. Priority order dequeues the items with the highest priority first.

What is queue data structure?

A queue is a collection of objects (a linear collection) inserted and removed using the first-in-first-out (FIFO) principle. Both the ends are open in the queue data structure.

Why is stack used in C++?

The stack is a fundamental data structure for storing elements linearly. The operations on the stack are carried out in the LIFO (last in, first out) order. This means that the last element added to the stack will be the first to be removed.

Conclusion

So, this article discussed the approach to the problem string rearrangement with the help of a priority queue and another efficient method in the C++ programming language.

If you are a beginner, interested in coding, and want to learn DSA, you can look for our guided path for DSA, which is free!