In Reorganize String problem we have given a string containing some characters “a-z” only. Our task is to rearrange those characters such that no two same characters are adjacent to each other.
Table of Contents
Example
Input
apple
Output
pelpa
Input
book
Output
obko
Input
aa
Output
not possible
Input
aaab
Output
not possible
Explanation for Reorganize String
To solve this problem we shall implement a priority queue by using max heap in which we have to put the highest frequency character first(greed approach). After that, we will put all the characters in our priority queue/max heap and ordered by their frequency(highest frequency character at the root). The character with the highest frequency will be taken from the heap and will be added to the resultant string. The frequency of that character will be reduced and that character will be popped out of the priority queue.
Algorithm for Reorganize String
- Initialize a priority queue using max heap, “pq” which will store character with their frequencies.
- Create a temporary key which will work as the previously visited element in the resultant string. Initialize it {char = ‘$’, freq = -1}
- While “pq” is not empty.
- An element will be popped and added to the result.
- Decrease frequency of popped element by 1.
- Push the previous element back into the priority queue if it’s frequency > “0”.
- Make the current element as the previous element for the next iteration.
- Print “Not Possible” if the length of the original string and the resulting string is not equal. Else print result.
First, we make a class name key in which we could store the frequency of characters. After that, we override our compare method of Comparator interface such that, we could order all character by their frequencies. Then we make a function to rearrange our string in which we make priority queue “pq” to store characters in it and use keycomparator() class to order character according to their frequencies and then traversing our queue through while loop so we could rearrange characters and finally compare the size of the original string and resultant string to get our rearranged string.
Implementation in C++
#include<iostream>
#include<queue>
using namespace std;
const int MAX_CHAR = 26;
struct Key
{
int freq; // store frequency of character
char ch;
// function for priority_queue to store Key
// according to freq
bool operator<(const Key &k) const
{
return freq < k.freq;
}
};
// Function to rearrange character of a string
// so that no char repeats twice
string Rearrange_String(string str)
{
int original_size = str.length();
// Store frequencies of all characters in string
int count[MAX_CHAR] = {0};
for (int i = 0 ; i < original_size; i++)
count[str[i]-'a']++;
// Insert all characters with their frequencies
// into a priority_queue
priority_queue< Key > pq;
for (char c = 'a' ; c <= 'z' ; c++)
{
if (count[c-'a'])
{
pq.push( Key { count[c-'a'], c} );
}
}
// 's' that will store resultant value
string s = "" ;
// work as the previous visited element
// initial value for previous element be. ( '$' and
// it's freq '-1' )
Key prev {-1, '$'} ;
// traversing queue
while (!pq.empty())
{
// pop the top element from queue
// add it to string 's'.
Key k = pq.top();
pq.pop();
s = s + k.ch;
// If frequency of previous character < 0
// we need not to push it
if (prev.freq > 0)
pq.push(prev);
// make current character as the previous character
// decrease frequency by 1
(k.freq)--;
prev = k;
}
// If length of the final string and original
// string is not same then it is not possible to rearrange.
if (original_size != s.length())
return "Not Possible";
else
// valid string
return s;
}
// main function to test above function
int main()
{
string str = "apple" ;
cout<<Rearrange_String(str);
return 0;
}plaep
Implementation in Java
/* Java program to Reorganize string in such manner,
there should no same two adjacent string
*/
import java.io.*;
import java.util.*;
class Key {
int freq; // store frequency of character
char ch;
Key(int val, char c) {
freq = val;
ch = c;
}
}
class KeyComparator implements Comparator<Key> {
// Overriding compare()method of Comparator
public int compare(Key k1, Key k2) {
if (k1.freq<k2.freq)
return 1;
else if (k1.freq > k2.freq)
return -1;
return 0;
}
}
class reorganize_string {
static int MAX_CHAR = 26;
// Function to rearrange character of a string
// so that no char repeats twice
static String Rearrange_String(String str) {
int original_size = str.length();
// Store frequencies of all characters in string
int[] count = new int[MAX_CHAR];
for (int i = 0; i<original_size; i++)
count[str.charAt(i) - 'a']++;
// Insert all characters with their frequencies
// into a priority_queue
PriorityQueue<Key> pq = new PriorityQueue<>(new KeyComparator());
for (char c = 'a'; c<= 'z'; c++) {
int val = c - 'a';
if (count[val] > 0)
pq.add(new Key(count[val], c));
}
// 's' that will store resultant value
String s = "";
// work as the previous visited element
// initial value for previous element be. ( '$' and
// it's freq '-1' )
Key prev = new Key(-1, '$');
// traversing queue
while (pq.size() != 0) {
// pop the top element from queue
// add it to string 's'.
Key k = pq.peek();
pq.poll();
s = s + k.ch;
// If frequency of previous character<0
// we need not to push it
if (prev.freq > 0)
pq.add(prev);
// make current character as the previous character
// decrease frequency by 1
(k.freq) --;
prev = k;
}
// If length of the final string and original
// string is not same then it is not possible to rearrange.
if (original_size != s.length())
return "Not Possible";
else
return s;
}
// main func to test above function
public static void main(String args[]) {
String str = "apple";
System.out.println(Rearrange_String(str));
}
}pelpa
Complexity Analysis for Reorganize String
Time Complexity
O(n log A) where n is the length of string and A is the size of alphabets
Space Complexity
O(A) where A is the size of the alphabets.