# Reorganize String
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/reorganize-string)
Canonical: https://scaleengineer.com/dsa/problems/reorganize-string
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy), [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Hash Table, String, Heap (Priority Queue)
**Companies:** [Intuit](https://scaleengineer.com/companies/intuit), [PayPal](https://scaleengineer.com/companies/paypal), [Roblox](https://scaleengineer.com/companies/roblox), [Walmart Labs](https://scaleengineer.com/companies/walmart-labs), [eBay](https://scaleengineer.com/companies/ebay), [Coupang](https://scaleengineer.com/companies/coupang), [Tesla](https://scaleengineer.com/companies/tesla), [Citadel](https://scaleengineer.com/companies/citadel), [Pinterest](https://scaleengineer.com/companies/pinterest), [Druva](https://scaleengineer.com/companies/druva)
---
## Problem
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.

# Approaches
## Brute Force with Permutations
This approach generates all possible unique permutations of the input string and checks each one to see if it meets the condition that no two adjacent characters are the same. The first valid permutation found is returned. If no such permutation exists after checking all possibilities, it means a reorganization is not possible.
**Time:** O(n! * n), where n is the length of the string. In the worst case, we might generate up to n! unique permutations, and for each, we might perform operations proportional to n. This is not a practical solution. · **Space:** O(n), where n is the length of the string. This space is used for the recursion stack and to store the state of the permutation being built.
**Pros:** Conceptually simple to understand.
**Cons:** Extremely inefficient due to factorial time complexity.; Will time out for all but the smallest input strings (e.g., n > 10).
### Explanation
The brute-force method involves exploring every single arrangement of the characters in the string `s`. This can be achieved using a backtracking algorithm. We would try to build a valid string character by character. At each position, we would try to place an available character, ensuring it's not the same as the character at the previous position. If we successfully build a string of the same length as `s`, we have found a solution. If we explore all possibilities and fail to do so, no solution exists. Due to the massive number of permutations (n!), this approach is computationally infeasible for the given constraints.
### Algorithm
- This approach is not implemented due to its extreme inefficiency. The general algorithm would be:
- 1. Define a recursive function, say `generatePermutations`, that explores all possible orderings of the characters in `s`.
- 2. To handle duplicate characters, use a frequency map of characters rather than swapping elements in an array to generate unique permutations.
- 3. In the recursive function, at each step, try to append every available character (from the frequency map) to the current permutation string.
- 4. Before appending, check if the character is the same as the last character added. If it is, skip this choice.
- 5. Once a permutation of length `n` is formed, it is a valid solution. Return it.
- 6. If the recursion completes without finding a solution, it's impossible.

## Greedy Approach with Max Heap
A more efficient method is a greedy approach using a max heap (Priority Queue). The idea is to always append the most frequent available character that is different from the previously appended character. This ensures that we use up the characters that are most likely to cause a conflict (i.e., the most frequent ones) as early as possible, maximizing our chances of finding a valid arrangement.
**Time:** O(n log A), where n is the length of the string and A is the size of the character set. Counting frequencies is O(n). Building the heap is O(A log A). The main loop runs n times, with each iteration involving heap operations (poll and add) that take O(log A) time. Since A is a constant (26), this is effectively O(n). · **Space:** O(A) or O(1), where A is the size of the character set (26). The space is used for the frequency map and the heap, both of which are bounded by the constant alphabet size.
**Pros:** Significantly more efficient than brute force.; Guaranteed to find a solution if one exists.; Excellent space complexity, as it only depends on the alphabet size.
**Cons:** Slightly more complex to implement than a direct array-based approach.; The time complexity has a logarithmic factor related to the alphabet size, making it slightly slower in theory than the most optimal O(n) solution.
### Explanation
This greedy strategy works by prioritizing the most frequent characters. A max heap is the perfect data structure for this, as it always provides the element with the highest priority (in this case, frequency) in O(log A) time, where A is the alphabet size.

The core of the algorithm is to iteratively build the result string. In each step, we extract the most frequent character from the heap and append it to our result. To ensure no two adjacent characters are the same, we don't immediately put this character back into the heap. Instead, we hold onto it and only add it back in the *next* iteration, after we've appended a *different* character. This ensures separation. We repeat this process until the heap is empty.

An initial check is crucial: if any character appears more than `(n + 1) / 2` times, it's impossible to arrange them without two being adjacent. This is because to separate `k` instances of a character, you need at least `k - 1` other characters to place in between.

```java
class Solution {
    public String reorganizeString(String s) {
        Map<Character, Integer> counts = new HashMap<>();
        for (char c : s.toCharArray()) {
            counts.put(c, counts.getOrDefault(c, 0) + 1);
        }

        PriorityQueue<Character> maxHeap = new PriorityQueue<>((a, b) -> counts.get(b) - counts.get(a));
        maxHeap.addAll(counts.keySet());

        // Check for impossibility
        if (counts.get(maxHeap.peek()) > (s.length() + 1) / 2) {
            return "";
        }

        StringBuilder res = new StringBuilder();
        char prev = ' '; // Placeholder for previous character
        int prevCount = 0;

        while (!maxHeap.isEmpty()) {
            char current = maxHeap.poll();
            res.append(current);
            
            // Add the previous character back to the heap if it still has counts left
            if (prev != ' ' && prevCount > 0) {
                maxHeap.add(prev);
            }

            // Update previous character to be the current one for the next iteration
            prev = current;
            prevCount = counts.get(current) - 1;
            counts.put(current, prevCount);
        }

        return res.toString();
    }
}
```
### Algorithm
- 1. **Count Frequencies**: Create a frequency map (e.g., a `HashMap` or an array of size 26) to store the counts of each character in `s`.
- 2. **Check for Impossibility**: Find the maximum frequency `maxFreq`. If `maxFreq > (n + 1) / 2`, where `n` is the length of `s`, return `""` as no solution is possible.
- 3. **Build Max Heap**: Create a `PriorityQueue` to act as a max heap. Populate it with pairs of `(frequency, character)` for all characters with a count greater than zero. The heap should be ordered by frequency in descending order.
- 4. **Construct the String**: Initialize an empty `StringBuilder`.
- 5. **Greedy Selection Loop**: While the heap is not empty:
  - Poll the element with the highest frequency, let's call it `current`.
  - Append `current.character` to the `StringBuilder`.
  - If a `previous` element (the one polled in the last iteration) exists and its decremented frequency is greater than 0, add it back to the heap. This one-step delay prevents the same character from being chosen twice in a row.
  - Decrement the frequency of `current`.
  - Set `previous = current`.
- 6. **Return Result**: Convert the `StringBuilder` to a string and return it.

## Greedy Approach with Interleaving Placement
The most optimal approach is a clever greedy strategy that directly constructs the result string without needing a complex data structure like a heap. It first identifies the most frequent character and places all its instances into the new string at even-numbered indices (0, 2, 4, ...). This maximizes their separation. Then, it places all the remaining characters into the remaining slots (starting from odd-numbered indices 1, 3, 5, ...).
**Time:** O(n + A) or simply O(n), where n is the string length and A is the alphabet size. We perform a few passes: one to count frequencies (O(n)), one to find the max frequency character (O(A)), and one more to place all characters into the result array (O(n)). · **Space:** O(n + A) or simply O(n). We use an O(A) or O(1) array for frequencies and an O(n) character array to build the result string. The space for the result is dominant.
**Pros:** Most efficient in terms of time complexity (true O(n)).; Simple and elegant logic once the interleaving pattern is understood.; Avoids the overhead of a Priority Queue.
**Cons:** Uses O(n) extra space for the result array, which is more than the heap-based approach's O(1) space.
### Explanation
This method is based on the same greedy principle but uses a more direct construction. The key insight is that if a solution is possible, the most frequent character is the biggest obstacle. By placing it first with maximum spacing (i.e., at every other position), we create slots between them. Then, we can fill these slots and the remaining positions with the rest of the characters.

For example, if 'a' is the most frequent character in 'aaabcc', we would first place the 'a's: `a _ a _ a _`. Then we fill the blanks with the other characters: `a b a c a c`. This strategy guarantees a valid arrangement if one exists, because the initial check (`maxFreq <= (n + 1) / 2`) ensures we have enough other characters to fill the gaps between the most frequent one.

```java
class Solution {
    public String reorganizeString(String s) {
        int n = s.length();
        int[] counts = new int[26];
        for (char c : s.toCharArray()) {
            counts[c - 'a']++;
        }

        int maxFreq = 0;
        int maxCharIndex = 0;
        for (int i = 0; i < 26; i++) {
            if (counts[i] > maxFreq) {
                maxFreq = counts[i];
                maxCharIndex = i;
            }
        }

        if (maxFreq > (n + 1) / 2) {
            return "";
        }

        char[] res = new char[n];
        int index = 0;

        // 1. Place the most frequent character
        while (counts[maxCharIndex] > 0) {
            res[index] = (char) (maxCharIndex + 'a');
            index += 2;
            counts[maxCharIndex]--;
        }

        // 2. Place the rest of the characters
        for (int i = 0; i < 26; i++) {
            while (counts[i] > 0) {
                if (index >= n) {
                    index = 1; // Wrap around to fill odd indices
                }
                res[index] = (char) (i + 'a');
                index += 2;
                counts[i]--;
            }
        }

        return new String(res);
    }
}
```
### Algorithm
- 1. **Count Frequencies**: Create an integer array `counts` of size 26 to store the frequency of each character ('a' through 'z').
- 2. **Find Most Frequent**: Iterate through the `counts` array to find the character with the highest frequency (`maxFreq`) and its corresponding character (`maxChar`).
- 3. **Check for Impossibility**: If `maxFreq > (n + 1) / 2`, return `""`.
- 4. **Initialize Result Array**: Create a character array `res` of size `n`.
- 5. **Place Most Frequent Character**: Place all instances of `maxChar` into the `res` array at even indices (0, 2, 4, ...). Keep track of the current index.
- 6. **Place Remaining Characters**: Iterate through the `counts` array again (from 'a' to 'z'). For each character:
  - While its count is greater than 0, place it into the `res` array.
  - If the index for placement goes beyond the array bounds, reset it to 1 (to start filling odd positions).
  - Place the character and advance the index by 2.
  - Decrement the character's count.
- 7. **Return Result**: Convert the `res` character array into a string and return it.

# Solutions
### Java

```java
class Solution {
public
  String reorganizeString(String s) {
    int[] cnt = new int[26];
    int mx = 0;
    for (char c : s.toCharArray()) {
      int t = c - 'a';
      ++cnt[t];
      mx = Math.max(mx, cnt[t]);
    }
    int n = s.length();
    if (mx > (n + 1) / 2) {
      return "";
    }
    int k = 0;
    for (int v : cnt) {
      if (v > 0) {
        ++k;
      }
    }
    int[][] m = new int[k][2];
    k = 0;
    for (int i = 0; i < 26; ++i) {
      if (cnt[i] > 0) {
        m[k++] = new int[]{cnt[i], i};
      }
    }
    Arrays.sort(m, (a, b)->b[0] - a[0]);
    k = 0;
    StringBuilder ans = new StringBuilder(s);
    for (int[] e : m) {
      int v = e[0], i = e[1];
      while (v-- > 0) {
        ans.setCharAt(k, (char)('a' + i));
        k += 2;
        if (k >= n) {
          k = 1;
        }
      }
    }
    return ans.toString();
  }
}

```

### CPP

```cpp
class Solution {
public:
  string reorganizeString(string s) {
    vector<int> cnt(26);
    for (char &c : s)
      ++cnt[c - 'a'];
    int mx = *max_element(cnt.begin(), cnt.end());
    int n = s.size();
    if (mx > (n + 1) / 2)
      return "";
    vector<vector<int>> m;
    for (int i = 0; i < 26; ++i) {
      if (cnt[i])
        m.push_back({cnt[i], i});
    }
    sort(m.begin(), m.end());
    reverse(m.begin(), m.end());
    string ans = s;
    int k = 0;
    for (auto &e : m) {
      int v = e[0], i = e[1];
      while (v--) {
        ans[k] = 'a' + i;
        k += 2;
        if (k >= n)
          k = 1;
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def reorganizeString(self, s: str) -> str: n = len(s) cnt = Counter(s) mx = max(cnt . values()) if mx > (n + 1) // 2: return '' i = 0 ans = [None] * n for k, v in cnt . most_common(): while v: ans[i] = k v -= 1 i += 2 if i >= n: i = 1 return '' . join(ans)

```