Reorganize String

medium hash map string greedy heap counting

Problem

Given string s, rearrange it so no two adjacent characters are equal. Return any valid rearrangement, or "" if impossible (some letter's count exceeds ⌈n/2⌉).

Inputs = "aab"

Output"aba"

'a' appears 2 ≤ ⌈3/2⌉ = 2 times, so a valid arrangement exists.

import heapq
from collections import Counter

def reorganize_string(s):
    cnt = Counter(s)
    if max(cnt.values()) > (len(s) + 1) // 2:
        return ""
    heap = [(-c, ch) for ch, c in cnt.items()]
    heapq.heapify(heap)
    out = []
    while len(heap) >= 2:
        c1, ch1 = heapq.heappop(heap)
        c2, ch2 = heapq.heappop(heap)
        out.append(ch1); out.append(ch2)
        if c1 + 1: heapq.heappush(heap, (c1 + 1, ch1))
        if c2 + 1: heapq.heappush(heap, (c2 + 1, ch2))
    if heap:
        out.append(heap[0][1])
    return "".join(out)

function reorganizeString(s) {
  const cnt = {};
  for (const c of s) cnt[c] = (cnt[c] || 0) + 1;
  const maxC = Math.max(...Object.values(cnt));
  if (maxC > ((s.length + 1) >> 1)) return "";
  const heap = Object.entries(cnt).map(([c, n]) => [n, c]);
  const pop = () => { heap.sort((a, b) => b[0] - a[0]); return heap.shift(); };
  let out = "";
  while (heap.length >= 2) {
    const [n1, c1] = pop();
    const [n2, c2] = pop();
    out += c1 + c2;
    if (n1 - 1 > 0) heap.push([n1 - 1, c1]);
    if (n2 - 1 > 0) heap.push([n2 - 1, c2]);
  }
  if (heap.length) out += heap[0][1];
  return out;
}

class Solution {
    public String reorganizeString(String s) {
        int[] cnt = new int[26];
        for (char c : s.toCharArray()) cnt[c - 'a']++;
        int max = 0;
        for (int v : cnt) max = Math.max(max, v);
        if (max > (s.length() + 1) / 2) return "";
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[0] - a[0]);
        for (int i = 0; i < 26; i++) if (cnt[i] > 0) pq.offer(new int[]{cnt[i], i});
        StringBuilder sb = new StringBuilder();
        while (pq.size() >= 2) {
            int[] a = pq.poll(), b = pq.poll();
            sb.append((char)(a[1] + 'a')); sb.append((char)(b[1] + 'a'));
            if (--a[0] > 0) pq.offer(a);
            if (--b[0] > 0) pq.offer(b);
        }
        if (!pq.isEmpty()) sb.append((char)(pq.poll()[1] + 'a'));
        return sb.toString();
    }
}

class Solution {
public:
    string reorganizeString(string s) {
        vector<int> cnt(26, 0);
        for (char c : s) cnt[c - 'a']++;
        int mx = *max_element(cnt.begin(), cnt.end());
        if (mx > ((int)s.size() + 1) / 2) return "";
        priority_queue<pair<int, int>> pq;
        for (int i = 0; i < 26; i++) if (cnt[i]) pq.push({cnt[i], i});
        string out;
        while ((int)pq.size() >= 2) {
            auto a = pq.top(); pq.pop();
            auto b = pq.top(); pq.pop();
            out += ('a' + a.second); out += ('a' + b.second);
            if (--a.first > 0) pq.push(a);
            if (--b.first > 0) pq.push(b);
        }
        if (!pq.empty()) out += ('a' + pq.top().second);
        return out;
    }
};

Explanation

To keep equal letters apart, the trick is to always place the two most common letters next to each other. Two different letters never clash, and by spending the frequent ones early we stop any single letter from piling up at the end. A max-heap always hands us the current most common letter.

First we count every letter. If any letter appears more than ⌈n/2⌉ times, it cannot be spread out, so we immediately return "". Otherwise we push (count, char) pairs into a max-heap.

Each round we pop the top two letters, append both to the result, decrease each count by one, and push them back if any copies remain. Because the two letters are always different, adjacent characters in the output never match.

Example: s = "aab". Counts are a:2, b:1. Pop a and b, append "ab"; a still has one left. Now only a remains in the heap, so we append it once to get "aba".

When a single letter is left at the end (an odd total), it is safe to append it once, because the feasibility check guaranteed it cannot collide with the previous character.

Time: O(n log k) Space: O(k)