Rearranging String

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.

1. int i = 0;
   We are storing rearrangement from the first index, obviously, in the input string itself.
2. pair<int, char> prev = max_heap.top(); max_heap.pop();
   Create a pair to store the first top pair of max_heap
3. 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;
}

You can also try this code with Online C++ Compiler

Run Code

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.

Also Read, Prefix Sum Array

Odd-even position approach

Steps:-

1. First, we find the most frequent character.
2. 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.
3. Start filling the most frequent character at alternate places starting from the index 0(even indexes), eg: 0,2,4,6 .....
4. Start filling the other characters with a gap of 1 index, from where the most frequent element got exhausted(continue for even indexes).
5. 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;
}

You can also try this code with Online C++ Compiler

Run Code

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.

Check out this article - C++ String Concatenation

Frequently Asked Questions

What is a priority queue?

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! 

Recommended problems -

• Beautiful String
• Subsequence of a String
• Find the Shortest Substring in a String

Recommended Reading:

• Python String Concatenation
• Introduction to Python
• Car Pooling
• Heap
• Min Heap and Max Heap Data Structure
• Rearrange a Binary String as Alternative X and Y occurrences
• Kth Smallest Element in Unsorted Array using Priority Queue
• Applications of Priority Queue
• Practise Problems

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, Basics of C++, Basics of Java, Basics of Python, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

In case of any comments or suggestions, feel free to post them in the comments section.