Reorganize String
Difficulty: Medium
Category: DSA
Topics: Hash Table, String, Greedy, Sorting, Heap (Priority Queue), Counting
Asked at: Amazon, Google, Facebook, Microsoft, Wish, Uber, Goldman Sachs
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_.
**Example 1:**
**Input:** s = "aab"
**Output:** "aba"
```
**Example 2:**
**Input:** s = "aaab"
**Output:** ""
```
**Constraints:**
- `1 <= s.length <= 500`
- `s` consists of lowercase English letters.