# 767. Reorganize String

## Problem Statement

<br>

Given a string `s`, rearrange the characters of `s` so that any two adjacent characters are not the same.

Return *any possible rearrangement of* `s` *or return* `""` *if not possible*.

&#x20;

**Example 1:**

<pre><code><strong>Input: s = "aab"
</strong><strong>Output: "aba"
</strong></code></pre>

**Example 2:**

<pre><code><strong>Input: s = "aaab"
</strong><strong>Output: ""
</strong></code></pre>

&#x20;

**Constraints:**

* `1 <= s.length <= 500`
* `s` consists of lowercase English letters.

## Intuition

```
Approach:
Maintain count of all the things and then start placing the things alternatively 
on the basis of frequency 

Three conditions- 1) highest frequency element > len/2 -> not possible
As it cannot take alternating position
______
a a a   if a is 4 times then not possible

Else once completed , start from index 1 and fill till end
```

### Links

<https://leetcode.com/problems/reorganize-string/description/>

### Video Links

### Approach 1:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Solution {
public:
    string reorganizeString(string s) {
        unordered_map<char,int> mp;
        priority_queue<pair<int, char>> pq;
        for(auto &it: s)
            mp[it]++;

        for(auto &it: mp){
            char alp = it.first;
            int count = it.second;

            pq.push({count, alp});
        }

        string temp(s.size(),'X');
        int count=pq.top().first;

        if(count > (s.size()+1)/2)
            return "";

        int index = 0;
        char alp = pq.top().second;

        while(count--){
            temp[index] = alp;
            index+=2;
        }

        if(pq.top().first == (s.size()+1)/2)
            index = 1;

        pq.pop();

        while(!pq.empty()){
            int count = pq.top().first;
            char alp = pq.top().second;

            while(count--){
                if(index >= temp.size())
                    index = 1;
                temp[index] = alp;
                index+=2;
            }
            pq.pop();
        }

        return temp;
    }
};
```

{% endcode %}

### Approach 2:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 3:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 4:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Similar Problems

###