# LC 767. Reorganize String

### [Problem link](https://leetcode.com/problems/reorganize-string/)

###### tags: `leedcode` `medium` `c++`

Given a string <code>s</code>, rearrange the characters of <code>s</code> so that any two adjacent characters are not the same.

Return any possible rearrangement of <code>s</code> or return <code>""</code> if not possible.

**Example 1:**

Input: s = "aab"
Output: "aba"

**Example 2:**

Input: s = "aaab"
Output: ""

**Constraints:**

- <code>1 <= s.length <= 500</code>
- <code>s</code> consists of lowercase English letters.

## Solution 1 - Min Heap
#### C++

class Solution {
public:
    string reorganizeString(string s) {
        vector<int> charCnt(26, 0);
        for (char& c: s) {
            charCnt[c - 'a']++;
        }

        priority_queue<vector<int>> pq;
        for (int i = 0; i < 26; i++) {
            if (charCnt[i] > 0) {
                pq.push({charCnt[i], i + 'a'});
            }
        }

        string ans;
        while (!pq.empty()) {
            vector<int> first = pq.top();  // first: [charCnt, char]
            pq.pop();
            if (ans.empty() || ans.back() != first[1]) {
                ans += char(first[1]);
                if (--first[0] > 0) {
                    pq.push(first);
                }
            } else {
                if (pq.empty()) {
                    return "";
                }
                vector<int> second = pq.top();
                pq.pop();
                ans += char(second[1]);
                if (--second[0] > 0) {
                    pq.push(second);
                }
                pq.push(first);
            }
        }
        return ans;
    }
};

>### Complexity
>n = s.length
>| | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1 | O(nlogn) | O(26) |

## Note
x