Skip to main content

767. Reorganize String

medium

Rearrange the characters of a string so that no two adjacent characters are the same — or return an empty string if it's impossible. A clean max-heap greedy with a feasibility check.

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

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
""

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Feasibility first: if any character appears more than (n + 1) / 2 times, no valid arrangement exists.

Hint 2

Greedy intuition: always place the most-frequent remaining character next — as long as it isn't the one you just placed.

Hint 3

Max-heap by count. Pop the top, append its char, decrement and hold it aside. Then pop the next, append it, decrement, and push the held one back. Repeat.

Solution approach

Reveal approach

Feasibility check first: count character frequencies; if any frequency exceeds (n + 1) / 2, return empty string — pigeonhole says you can't avoid an adjacent collision. Otherwise, push all (count, char) pairs into a max-heap keyed on count. Loop: pop two entries, append both characters to the result, decrement each count, and push back any with count > 0. If only one entry remains and its count is still > 1, return empty (shouldn't happen after the feasibility check, but defensive). Continue until the heap is empty or contains one entry of count 1 (append it and stop). Time O(n log a) where a is the alphabet size (effectively O(n)), space O(a). Counting-sort + interleaving is an O(n) alternative if a is small and fixed.

Complexity

Time
O(n log a)
Space
O(a)

Related patterns

  • heap
  • greedy
  • counting

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Meta
  • Google

Practice these live with InterviewChamp.AI

Drill Reorganize String and Heaps problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →