Skip to main content

767. Reorganize String

mediumAsked at Pinterest

Reorganize String is Pinterest's go-to greedy + heap problem: given a string s, rearrange it so no two adjacent characters are the same. The interviewer wants the count-then-emit-highest pattern using a max-heap by frequency.

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

Source citations

Public interview reports confirming this problem appears in Pinterest loops.

  • Glassdoor (2026-Q1)— Pinterest SWE onsite reports cite Reorganize String as the greedy / heap round.
  • LeetCode Pinterest tag (2026-Q1)— On the Pinterest company-tagged problem list.

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 an empty string 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
''

Explanation: Impossible — 'a' appears 3 times in a 4-char string.

Approaches

1. Greedy with max-heap by frequency (optimal)

Count character frequencies. Push (count, char) into a max-heap by count. Repeatedly pop the two most-frequent, emit them in sequence, decrement counts, push back if count > 0.

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

function reorganizeString(s) {
  const freq = new Map();
  for (const ch of s) freq.set(ch, (freq.get(ch) || 0) + 1);
  // Feasibility: any char count > (n+1)/2 makes it impossible.
  for (const [, c] of freq.entries()) {
    if (c > Math.ceil(s.length / 2)) return '';
  }
  const heap = new MaxHeap();
  for (const [ch, c] of freq.entries()) heap.push({ ch, count: c });
  const out = [];
  while (heap.size() >= 2) {
    const a = heap.pop();
    const b = heap.pop();
    out.push(a.ch, b.ch);
    if (--a.count > 0) heap.push(a);
    if (--b.count > 0) heap.push(b);
  }
  if (heap.size()) out.push(heap.pop().ch);
  return out.join('');
}

Tradeoff: The greedy invariant: at every step, emit the two MOST-frequent remaining characters. Popping two ensures no immediate repeat. The pre-check (max count > ceil(n/2)) lets you fail fast on impossible inputs.

2. Index-stride placement (no heap)

Sort characters by frequency descending. Place the most-frequent character at even indices 0, 2, 4 ... then the next at the remaining indices.

Time
O(n log k)
Space
O(n)
function reorganizeStringStride(s) {
  const freq = new Array(26).fill(0);
  for (const ch of s) freq[ch.charCodeAt(0) - 97] += 1;
  const n = s.length;
  let maxIdx = 0;
  for (let i = 0; i < 26; i++) if (freq[i] > freq[maxIdx]) maxIdx = i;
  if (freq[maxIdx] > Math.ceil(n / 2)) return '';
  const out = new Array(n);
  let idx = 0;
  // Place the most-frequent at even indices first
  while (freq[maxIdx] > 0) {
    out[idx] = String.fromCharCode(97 + maxIdx);
    idx += 2;
    freq[maxIdx] -= 1;
  }
  // Fill remaining at even-then-odd
  for (let i = 0; i < 26; i++) {
    while (freq[i] > 0) {
      if (idx >= n) idx = 1;
      out[idx] = String.fromCharCode(97 + i);
      idx += 2;
      freq[i] -= 1;
    }
  }
  return out.join('');
}

Tradeoff: Skips the heap entirely — O(n) after a one-time max scan. Slightly trickier to reason about; some interviewers prefer the heap version because the invariant is clearer.

Pinterest-specific tips

Pinterest interviewers like the explicit feasibility pre-check: 'before I attempt rearrangement, I'll check whether any character appears more than ceil(n/2) times — if so, it's impossible.' Stating this upfront avoids running the heap to no useful end. Lead with the heap version because the invariant is easy to narrate; mention the index-stride version as an aside.

Common mistakes

  • Forgetting the feasibility check — the heap loop will dequeue and you'll emit duplicates without realizing it.
  • Popping ONE most-frequent and decrementing — adjacent chars become identical because you only avoid the previous emission, not the immediate next.
  • Off-by-one on the feasibility bound: 'a' appearing exactly ceil(n/2) times is FEASIBLE (consider 'aab').
  • Using a min-heap by mistake — you want max-frequency first.

Follow-up questions

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

  • K-distance reorganization (LeetCode 358) — adjacent chars must be >= k apart.
  • Sort Characters By Frequency (LeetCode 451).
  • Task Scheduler (LeetCode 621) — same primitive, different framing.
  • Multi-pass reorganization: minimize total adjacent-duplicate edits.

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 does pop-two-at-a-time work?

After emitting (a, b), neither is the most-frequent next iteration's adjacent emission. As long as no character ever exceeds half the remaining length, we can always find two distinct chars to emit.

Why does Pinterest like this problem?

Greedy + heap is a pattern that shows up in many Pinterest ranking and scheduling problems. This is the cleanest example: easy to state, satisfying to derive.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →