Reorganize String
Night-market stalls in a row. Each letter of s is a stall, and the letter is the dish it sells. Rearrange the stalls so that no two neighbours sell the same dish. Return any lineup that works, or the empty string "" when none does. Every valid lineup is accepted. Limits: 1 <= s.length <= 100000, lowercase letters a to z only. Hint: count the letters first, then decide where the most frequent one has to go. Examples: s = "aab" => "aba" s = "aaab" => "" (three a stalls cannot be kept apart by one b)
You're lining up the stalls of a night market. Each stall sells one dish, written as a lowercase letter, and the organiser wants no two neighbouring stalls to sell the same dish. You rearrange the stalls and return any lineup that works, or an empty string when no lineup exists. Interviewers like it because it looks like a sorting problem but is really about counting, and about knowing when to give up, and because the greedy choice has to be justified, not just coded. The classic trap is sorting the letters and spreading them out, or always taking the most common letter without remembering the one you just placed. Any valid lineup is accepted, and the string can hold up to 100,000 letters.
Examples
You write
reorganize_string(s: str)
Example 1
- Input
- s = "aab"
- returns
- "aba"
Example 2
- Input
- s = "aaab"
- returns
- ""
Save this for your laptop
The editor and Run need a bigger screen. The link opens Reorganize String ready to code. It is free, and the editor needs no account.
The pattern behind it
Strings
I reach for it when
- The input is text and the answer is a count, a substring or a new string.
- You need to compare, reverse or rebuild characters.
Say this before you type. Say which array pattern the string is hiding before you touch a character.
All 51 Strings problemsGreedy
I reach for it when
- A locally best choice looks safe.
- You sort first, then sweep once.
Say this before you type. Say the greedy choice, then say why swapping it for another choice cannot do better.
All 17 Greedy problems
Meet Coco
Coco is an AI study partner, not a person. She listens while you explain your code, asks what a line does and never hands you the fix. Sign in free to type with Coco, up to a daily limit, and to talk with her for one hour. After that, talking comes with the $79 pack. Anyone can open the editor and run their code.