Skip to main content

767. Reorganize String

mediumAsked at Amazon

Given a string, rearrange so no two adjacent chars are the same, or return empty if impossible. Amazon asks this to test whether you reach for a max-heap of (count, char) and articulate the 'highest-count first' greedy.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Amazon loops.

  • Glassdoor (2026-Q1)— Amazon SDE II onsite reports cite this as the heap-based greedy round.
  • Blind (2025-10)— Recurring Amazon interview problem.

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.

Constraints

  • 1 <= s.length <= 500
  • s consists of lowercase English letters.

Examples

Example 1

Input
s = "aab"
Output
"aba"

Example 2

Input
s = "aaab"
Output
""

Approaches

1. Max-heap of (count, char) (optimal)

Count chars. Push (count, char) into max-heap. Pop the top two each step; emit both; push back with count - 1 if still positive.

Time
O(n log k)
Space
O(k)
class MaxHeap {
  constructor() { this.data = []; }
  push(v) { this.data.push(v); this._up(this.data.length - 1); }
  pop() { if (!this.data.length) return; const top = this.data[0]; const last = this.data.pop(); if (this.data.length) { this.data[0] = last; this._down(0); } return top; }
  size() { return this.data.length; }
  _up(i) { while (i > 0) { const p = (i - 1) >> 1; if (this.data[p][0] >= this.data[i][0]) break; [this.data[p], this.data[i]] = [this.data[i], this.data[p]]; i = p; } }
  _down(i) { while (true) { const l = 2*i+1, r = 2*i+2; let best = i; if (l < this.data.length && this.data[l][0] > this.data[best][0]) best = l; if (r < this.data.length && this.data[r][0] > this.data[best][0]) best = r; if (best === i) break; [this.data[best], this.data[i]] = [this.data[i], this.data[best]]; i = best; } }
}

function reorganizeString(s) {
  const counts = new Map();
  for (const ch of s) counts.set(ch, (counts.get(ch) || 0) + 1);
  for (const [ch, c] of counts) if (c > Math.ceil(s.length / 2)) return '';
  const heap = new MaxHeap();
  for (const [ch, c] of counts) heap.push([c, ch]);
  const out = [];
  while (heap.size() >= 2) {
    const [c1, ch1] = heap.pop();
    const [c2, ch2] = heap.pop();
    out.push(ch1, ch2);
    if (c1 - 1 > 0) heap.push([c1 - 1, ch1]);
    if (c2 - 1 > 0) heap.push([c2 - 1, ch2]);
  }
  if (heap.size()) {
    const [c, ch] = heap.pop();
    if (c > 1) return '';
    out.push(ch);
  }
  return out.join('');
}

Tradeoff: Pop two at a time guarantees no immediate repeat. The early-exit check (any char count > ceil(n/2)) handles impossibility upfront.

2. Slot-filling (alternative)

Place the most-frequent char in even indices first (0, 2, 4, ...). Then fill the remaining chars in any order in odd indices (and the leftover even slots).

Time
O(n)
Space
O(n)
function reorganizeStringSlots(s) {
  const counts = new Map();
  for (const ch of s) counts.set(ch, (counts.get(ch) || 0) + 1);
  let maxCh = '', maxCnt = 0;
  for (const [ch, c] of counts) if (c > maxCnt) { maxCnt = c; maxCh = ch; }
  if (maxCnt > Math.ceil(s.length / 2)) return '';
  const result = new Array(s.length);
  let idx = 0;
  while (maxCnt-- > 0) { result[idx] = maxCh; idx += 2; }
  counts.delete(maxCh);
  for (const [ch, c] of counts) {
    let remaining = c;
    while (remaining > 0) {
      if (idx >= s.length) idx = 1;
      result[idx] = ch;
      remaining--;
      idx += 2;
    }
  }
  return result.join('');
}

Tradeoff: O(n) — beats the heap. Place the most-frequent char in even slots first to guarantee separation. Then fill the rest.

Amazon-specific tips

Amazon interviewers grade this on the impossibility check: if any char's count exceeds ceil(n/2), return empty immediately. State that upfront. Then offer either heap (general pattern) or slot-filling (O(n) but trickier). Both score the same; pick what you can write cleanly.

Common mistakes

  • Forgetting the impossibility check — heap or slots will silently produce an invalid result.
  • Popping one at a time from the heap (you must pop TWO to ensure no adjacent repeat).
  • Off-by-one in the slot indices (most-frequent char goes in even slots 0, 2, 4, ...).

Follow-up questions

An interviewer at Amazon may pivot to one of these next:

  • Task Scheduler (LC 621) — same heap pattern with cooldown.
  • What if the cooldown were variable (different per char)?
  • What if we needed minimal length (allowing dummy chars)?

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why is ceil(n/2) the cutoff?

If a char appears more than ceil(n/2) times, you can't separate every occurrence — at least two must be adjacent. With exactly ceil(n/2), they fit in alternating slots starting at index 0.

Heap or slots — which does Amazon prefer?

Both work. Heap is the general pattern that generalizes to Task Scheduler. Slot-filling is faster but problem-specific. Lead with whichever you can code cleanly.

Practice these live with InterviewChamp.AI

Drill Reorganize String and other Amazon interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →