Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem statement
3.
Approach - Using Max Heap
3.1.
Code in C++
3.2.
Complexity Analysis
4.
Odd-even position approach
4.1.
Code in C++
4.2.
Complexity Analysis
5.
Frequently Asked Questions
5.1.
What is a priority queue?
5.2.
What is queue data structure?
5.3.
Why is stack used in C++?
6.
Conclusion
Last Updated: Mar 27, 2024

Rearranging String

gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
Earn badges and level up

Introduction

This article will see the problem of rearranging strings and different approaches to solve this problem with examples and C++ code.

Also see, Data Structures

Problem statement

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.

Also check out - Substr C++

Get the tech career you deserve, faster!
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.
  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;
}
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.

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;
}
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.

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 -

 

Recommended Reading:

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.

Previous article
K Closest Points To Origin
Next article
Process Tasks Using Servers
Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass