Reorganize String

MediumHeapgreedy heap

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given a string s made up of lowercase English letters. Rearrange its characters so that **no two adjacent characters are the same**. Return any valid rearrangement of s. If it is impossible to rearrange the characters this way, return the empty string "". A rearrangement uses exactly the same multiset of characters as s — every letter must appear the same number of times it does in the original string, just in a different order. Because more than one valid answer may exist, your function should produce a deterministic result by always placing characters using the following greedy rule: repeatedly append the **most frequent remaining character** that is **different from the character just placed**; when two characters are tied in frequency, prefer the one that is **smaller alphabetically**. This produces a single well-defined output for any input.

Examples

Input: s = "aab"
Output: "aba"
The most frequent letter is `a` (count 2). Place `a`, then the next must differ so place `b`, then `a` again. No two neighbors match.
Input: s = "aaab"
Output: ""
`a` appears 3 times out of 4 characters. With only one other letter to separate them, at least two `a`s must touch, so no valid arrangement exists.
Input: s = "aabbcc"
Output: "abcabc"
All three letters tie at count 2. The greedy rule places them in alphabetical order each round, cycling a, b, c, a, b, c.

Constraints

  • `1 <= s.length <= 500`
  • `s` consists of lowercase English letters only (`'a'` to `'z'`).
  • Return `""` when no valid rearrangement is possible.

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.