What is the brute force approach and complexity for Reorganize String?

Try the arrangements of the letters in order; return the first with no equal neighbours with time complexity O(N · N!) and space complexity O(N).

What is the optimal approach and complexity for Reorganize String?

Max-heap of letter counts; each round writes the top two letters and holds them back with one copy less with optimal time complexity O(N log 26) and space complexity O(N).

How do you identify the pattern for Reorganize String?

Look for key signals in the prompt: "no two adjacent characters are the same" indicates Every copy of a letter needs a different letter after it. Each letter needs room.; "the most frequent letter" indicates The letter with the most copies runs out of room first, so its count decides whether an answer exists at all.; "return any valid answer, or the empty string" indicates One count gives the yes or no. The rest of the work builds one answer..

Reorganize String

Medium·LeetCode #767Basic Anchor

LeetCode

Jump:

30-Second Mental ModelGreedy — heap-assisted (max-heap by count, two letters per round)

Complexity:O(N · N!)→O(N log 26)

Key Insight

Check the most frequent letter first: if it appears more than (n + 1) / 2 times, return "". Otherwise keep a max-heap of (count, letter). Each round, pop the top two letters, write both, and push each back with one copy fewer. A leftover letter, if any, goes at the end.

Core Validity Invariant

Two neighbours must differ, and the most frequent letter can't be more than (n + 1) / 2. That second check is the only way the answer can be impossible, so it runs before anything else.

Problem

You get a string s. Rearrange its letters so that no two neighbours are the same letter.

Return any arrangement that works. If none exists, return the empty string "".

Input

A string s of lowercase English letters.

Output

A rearrangement of s with no two equal letters next to each other, or "" if that is impossible.

Example 1

Input: s = "aab"

Output: "aba"

aab and baa both have two a's side by side. Only aba works.

Example 2

Input: s = "aaab"

Output: ""

Three a's need a letter between each pair, so they need two separators. There is only one b.

Example 3

Input: s = "aaabbc"

Output: "abacba" (any valid arrangement is accepted)

The answer is not unique. Every a sits between two non-a letters.

Constraints

• 1 ≤ s.length ≤ 500
• `s` contains only lowercase English letters.

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
Which letter is the hardest to keep apart from itself? Does its count matter more than the others?
2.
A string of length 5 with three copies of one letter: can you space them out? What about length 4?
3.
When you place a letter, what is the only thing that decides whether the next letter is allowed?
4.
If you always place the letter with the most copies left, does that help or hurt you later?
5.
Could you place two letters at a time instead of one, and would that avoid some trouble?

Brute force approach

Idea

Sort the letters, then walk through every arrangement with next_permutation. Return the first one where no two neighbours are equal. If none passes, return "".

Thinking process

1
The answer is some rearrangement of the letters, so the simplest plan is to try them all.
2
Take aab. It has three arrangements: aab, aba, baa. The first and last have two a's side by side. aba passes, so that is the answer.
3
The number of arrangements grows as N!. For N = 500 that is impossible to try, so this only shows what the answer must look like.
4
If no arrangement passes, the loop ends and the answer is the empty string.

Visual

Each row is one arrangement of the letters. Red = two equal letters side by side. The brute keeps the first arrangement that has none.

Brute force: try arrangements until one workss = "aab"step 1/3

try 1

Tried so far

aab

Check

arrangement: aab
equal neighbours: yes

"aab" has a a side by side → next

In "aab" the two as touch, so this arrangement is no good. Try the next one.

Code & Implementation

brute.cpp

class Solution {
public:
    string reorganizeString(string s) {
        // Sorted first, so next_permutation visits every arrangement exactly once.
        sort(s.begin(), s.end());
        do {
            if (!hasEqualNeighbours(s)) return s;
        } while (next_permutation(s.begin(), s.end()));
        return "";  // every arrangement has two equal letters side by side
    }

private:
    bool hasEqualNeighbours(const string& t) {
        for (size_t i = 1; i < t.size(); i++)
            if (t[i] == t[i - 1]) return true;
        return false;
    }
};

Complexity

Time O(N · N!)Space O(N)

There are up to N! arrangements (fewer when letters repeat, because next_permutation skips equal copies). Each one costs N steps to check, and the string itself takes N space. Fine for N ≤ 8 only.

Optimized approach

Idea

Start from brute force

The brute force checks every full order. Most of those orders fail for one simple reason: two equal letters touch. We only need to know which letter may come next.

Find the repeated work

The brute force re-checks whole arrangements. The real question is local: after writing a letter, which one is allowed next? The one with the most copies left is always the safest pick, and a heap returns it in about log 26 steps.

Define the state — what variables do I need?

cnt[x]: How many copies of letter x are still to be written.
heap: Every letter that still has copies, ordered by (count, letter). The top has the most copies left.
res: The answer built so far.

Define validity

Two neighbours must differ, and the most frequent letter can't be more than (n + 1) / 2. That second check is the only way the answer can be impossible, so it runs before anything else.

Define the transitions — when does each pointer move, and why is it safe?

The heap holds 2 or more letters

Pop the top letter x and the next one y. Write x, then y. Push each back with one copy fewer, if it still has copies.

x and y are different letters, so the pair itself is safe. Because y's key is never above x's, y can't be the top of the next round, so no two equal letters meet across rounds.

The heap holds 1 letter

Write that letter at the end.

The feasibility argument below says its count is exactly 1, and it can't match the letter written just before it.

What does the current window add to the answer?

Each round adds two letters to res, so the answer grows by 2 per round. Each letter sits in the heap at most once.

Code & Implementation

optimal.cpp

class Solution {
public:
    string reorganizeString(string s) {
        int n = s.size();
        vector<int> cnt(26, 0);
        for (char c : s) cnt[c - 'a']++;

        // The most frequent letter needs a gap after every copy, so it can't be
        // more than (n + 1) / 2. If it is, no arrangement exists.
        if (*max_element(cnt.begin(), cnt.end()) > (n + 1) / 2) return "";

        // Max-heap of (count, letter). Ties go to the larger letter, so the order is fixed.
        priority_queue<pair<int, char>> pq;
        for (int c = 0; c < 26; c++)
            if (cnt[c] > 0) pq.push({cnt[c], char('a' + c)});

        string res;
        while (pq.size() >= 2) {
            // The two letters with the most copies left go next, one after the other.
            auto [c1, ch1] = pq.top(); pq.pop();
            auto [c2, ch2] = pq.top(); pq.pop();
            res += ch1;
            res += ch2;
            // Hold them back with one copy less. ch2 always sits below ch1 in the heap
            // (or is not pushed back at all), so ch2 can't be the top of the next round.
            if (--c1 > 0) pq.push({c1, ch1});
            if (--c2 > 0) pq.push({c2, ch2});
        }
        // One letter is left. The feasibility check means it has exactly one copy.
        if (!pq.empty()) res += pq.top().second;
        return res;
    }
};

Complexity

Time O(N log 26)Space O(N)

Counting is one pass over s. The heap never holds more than 26 letters, so each push or pop costs about log 26, a constant. The space is the output string, N characters. A linear version exists: sort the letters by count into one list, then write it into positions 0, 2, 4, … and then 1, 3, 5, …. It works because the most frequent letter fills only even slots, but the heap version is easier to get right.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	Try the arrangements of the letters in order; return the first with no equal neighbours	O(N · N!)	O(N)
Optimal	Max-heap of letter counts; each round writes the top two letters and holds them back with one copy less	O(N log 26)	O(N)

Why does this belong to this pattern?

Clues in the problem statement

“no two adjacent characters are the same”Every copy of a letter needs a different letter after it. Each letter needs room.
“the most frequent letter”The letter with the most copies runs out of room first, so its count decides whether an answer exists at all.
“return any valid answer, or the empty string”One count gives the yes or no. The rest of the work builds one answer.

Rearrange all letters+no two equal neighbours+most frequent ≤ (n + 1) / 2→Greedy — heap-assisted (max-heap by count, two letters per round)

This is the anchor of the heap-assisted sub-pattern. The best letter to place next changes after every round, because each placement lowers a count. A max-heap keeps the current best letter on top. The twist is that we place two letters per round, not one. Placing one at a time lets the same letter stay on top and end up next to itself (see the mistakes). Task Scheduler keeps a heap too, but it adds a cooldown; Hand of Straights uses a sorted map instead.

Don't make this mistake

Pattern confusion: writing each letter's copies as one block

✗ // sort letters by count, then write each one's copies in a row for (auto& [ch, c] : sortedByCount) res += string(c, ch);

✓ Use the heap: write two different letters per round and hold them back.

This is the layout for Sort Characters by Frequency, where neighbours don't matter. Here it fails at once: aaabbc gives aaabbc, and the three a's touch.

Popping one letter per round and not holding it back

✗ while (!pq.empty()) { auto [c, ch] = pq.top(); pq.pop(); res += ch; if (c > 1) pq.push({c - 1, ch}); }

✓ Pop two letters per round, write both, then push both back.

After one copy of a is written, a still has the most copies, so it is on top again and gets written again. On aaabc the output starts aacba, with two a's side by side. Holding back both letters of a round is what stops this.

Feasibility limit off by one

✗ if (maxCount > n / 2) return "";

✓ if (maxCount > (n + 1) / 2) return "";

For aba (n = 3, a appears 2 times), n / 2 = 1, so the wrong check returns "". But aba is a valid answer. The most frequent letter can take every other slot starting from the first, so (n + 1) / 2 is the real limit.

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Greedy translate into production architectures and low-level memory mechanics.

LLD Architecture