Reorganize String

---

Reorganize String: 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.

---

Try this Problem on your own or check similar problems:

1. Longest Happy String
2. Task Scheduler

Solution:

Java

public String reorganizeString(String s) {
    Map<Character, Integer> map = new HashMap<>();
    IntStream.range(0, s.length()).forEach(i -> map.put(s.charAt(i), map.getOrDefault(s.charAt(i), 0) + 1));

    PriorityQueue<Map.Entry<Character, Integer>> pq = new PriorityQueue<>((a, b) -> b.getValue() - a.getValue());
    pq.addAll(map.entrySet());
    Queue<Map.Entry<Character, Integer>> waitQueue = new LinkedList<>();

    StringBuilder sb = new StringBuilder();

    while(!pq.isEmpty()){
        Map.Entry<Character, Integer> entry = pq.poll();

        if(!sb.isEmpty() && sb.charAt(sb.length() - 1) == entry.getKey()) return "";

        sb.append(entry.getKey());

        if(waitQueue.size() > 0){
            pq.add(waitQueue.poll());
        }

        if(entry.getValue() - 1 == 0){
            map.remove(entry.getKey());
        }
        else {
            map.replace(entry.getKey(), entry.getValue() - 1);
            waitQueue.add(entry);
        }

    }

    return waitQueue.isEmpty() ? sb.toString() : "";
}

JavaScript

/**
 * @param {string} s
 * @return {string}
 */
var reorganizeString = function (s) {
  const freq = new Map();
  for (let i = 0; i < s.length; i++) {
    freq.set(s[i], (freq.get(s[i]) || 0) + 1);
  }

  const pq = new MaxPriorityQueue((a) => a[1]);
  for (const [char, count] of freq) {
    pq.enqueue([char, count], count);
  }

  const waitQueue = [];

  let result = "";
  while (!pq.isEmpty()) {
    const [char, count] = pq.dequeue().element;

    if (result.length > 0 && result[result.length - 1] === char) {
      return "";
    }

    result += char;

    if (waitQueue.length > 0) {
      const item = waitQueue.shift();
      pq.enqueue(item, item[1]);
    }

    if (count - 1 === 0) {
      freq.delete(char);
    } else {
      waitQueue.push([char, count - 1]);
    }
  }

  return waitQueue.length === 0 ? result : "";
};

Python

class Solution:
    def reorganizeString(self, s: str) -> str:
        freq = Counter(s)
        pq = []
        for key, value in freq.items():
            heapq.heappush(pq, (-value, key))

        waitQueue = deque()

        result = ""
        while pq:
            freq, char = heapq.heappop(pq)

            if result and result[-1] == char:
                return ""

            result += char

            if waitQueue:
                heapq.heappush(pq, waitQueue.popleft())

            freq += 1
            if freq != 0:
                waitQueue.append((freq, char))

        return result if not waitQueue else ""

C++

class Solution {
public:
    string reorganizeString(string s) {
        unordered_map<char, int> freq;
        for (char c : s) {
            freq[c]++;
        }

        auto comp = [](const pair<char, int>& a, const pair<char, int>& b) {
            return a.second < b.second;
        };
        priority_queue<pair<char, int>, vector<pair<char, int>>, decltype(comp)> pq(comp);
        for (auto& entry : freq) {
            pq.push(entry);
        }

        queue<pair<char, int>> waitQueue;

        string result;
        while (!pq.empty()) {
            pair<char, int> entry = pq.top();
            pq.pop();

            if (!result.empty() && result.back() == entry.first) {
                return "";
            }

            result.push_back(entry.first);

            if (!waitQueue.empty()) {
                pq.push(waitQueue.front());
                waitQueue.pop();
            }

            if (entry.second - 1 == 0) {
                freq.erase(entry.first);
            } else {
                entry.second -= 1;
                waitQueue.push(entry);
            }
        }

        return waitQueue.empty() ? result : "";
    }
};

---

Time/Space Complexity:

• Time Complexity: O(nlogn)
• Space Complexity: O(n)

---

Explanation:

This is a generalized solution to reorganizing string so that we can have gap x between same characters (for our case x = 1). We build a frequency map to track the occurrence of each character in string and we build a maxheap so that we have most frequent characters at top (note this a greedy approach just like we had in the solution for Task Scheduler). We also create a waitQueue after we used a character, we place it in the waiting queue so we can reuse it again after we filled the gap x with different characters (note that you could make the waiting queue wait for x > 1, in that scenario we would have a larger gap between same characters). If we have the same character at top of heap and last placed character in the new reorganized string, we know we can't make the arrangement of having a gap between same characters, so we return empty string. After we have placed the character in new string we check if we have placed all occurrences of that character and if we did, we remove it from the frequency map, otherwise we just decrement it's frequency and place it in the waiting queue again. We return the reorganized string only if we have placed all characters back and the waiting queue is empty (valid arrangement).