# Rearrange string

#### You are given a string “S”. Your task is to rearrange the characters of a string “S”, such that it does not contain any two adjacent characters which are the same.

#### If it is possible to rearrange the string “S”, then print any possible arrangement. else, print “not possible” without quotes.

#### For Example:

```
For a string “qaacde”, This string has two same adjacent characters.
So, one possible way to rearrange the string is “qacade”. Now, this string does not have two adjacent characters that are the same.
```

##### Input format :

```
The first line of input contains a single integer T, representing the number of test cases or queries to be run.
Then the T test cases follow.
The first line of each test case contains a string S.
```

##### Output format :

```
For each test case, the output will be “Yes” if you have returned the correct answer, else it will be “No”.
```

##### Note:

```
You do not need to print anything, it has already been taken care of. Just implement the given function.
```

##### Constraints :

```
1 <= T <= 10
0 <= |S| <= 10^5
Time Limit: 1 sec
```

In this approach, we will generate all the possible rearrangements of the string and check if the current string in our rearrangement does not have any two adjacent characters that are the same. If we can find any string which satisfies our criteria then we will return that string else we will return “not possible”.

We can implement the above approach by –

- Generate all permutations of a string.
- For each permutation check if this permutation does not have two characters that are the same, if yes then we will return the current permutation else we will move to the next permutation.
- If we are not able to find any valid arrangement, then we will return
**“not possible”**.

The idea is here to store the frequency of each character in a hashmap and then build a max heap of pairs containing the frequency of character and character.

We will always pick the highest frequency character that is not the same as the previously picked character from the max heap and add the picked character to the answer.

**Steps : **

- Declare an empty string as an ANSWER.
- Store frequency of each character in a hashmap or array, key as a character, and value as its frequency.
- Build a max heap of pairs where each pair contains the frequency of character as a key and character as value.
- Declare a variable PREV to store the previously picked element and initialize it with -1.
- Run a loop until the max heap is not empty and do
- Pop the top element from max heap and add the character of the popped element to ANSWER.
- Decrease frequency of popped element by 1.
- Push the previous element back to max heap if its frequency is greater than 0.
- Make a popped element as the previous element for the next iteration.

- If the length of the original string and ANSWER is not equal then return “not possible”.
- Else return the ANSWER.

The idea is here to sort the string based on the frequency of characters and then merge characters one by one from the front and middle of the string using **left **and **right **pointers.

**Steps : **

- Declare an empty string as an answer.
- Store the frequency of each character in a hashmap.
- Sort the given string based on the frequency of characters.
- Initialize left and
**right**pointer as LEFT**N**– 1)/2 + 1, where N is length of string. - Run a loop until LEFT<=(
**N**-1)/2 and do :- Add S
**[LEFT]**to answer and increment LEFT**= LEFT**+1. - If RIGHT
**N**then, Add S**[RIGHT]**to ANSWER and increment RIGHT**= RIGHT**+ 1.

- Add S
- Check if the ANSWER has any two adjacent characters that are the same, if yes then return
**“not possible”**else return an ANSWER.

The idea here is to store the frequency of each character of a string in a frequency array.

Let’s consider the following two observations:

- We can fill the same characters in either even positions or odd positions of string.
- The order of filling characters does not matter except for the highest frequency character.
- Let us denote the length of the string as
**N**. If the frequency of the highest frequency element in the string is greater than (**N+1)/2**then we cannot generate a string that does not have any two same characters.

So we will fill maximum frequency characters first in even positions and then remaining characters at odd positions. If all even positions are filled then we will start filling from odd positions.

**Steps : **

- Declare an empty string as an ANSWER.
- Declare an array of size 26 as HASH
**[26]**to store the frequency of each character. - Store frequency of each character of a string in HASH.
- Calculate the maximum frequency character using HASH. Let us denote it by MAX_FREQUENCY_CHARACTER
**.** - If HASH
**[MAX_FREQUENCY_CHARACTER]****>**(**N+1)/2**then return**“not possible”**. - Store all characters of MAX_FREQUENCY in even positions of ANSWER
**.** - Store remaining characters in even position of ANSWER and if all even positions are filled then use odd positions to store characters in ANSWER.
- Return ANSWER.