MediumHash TableStringGreedySortingHeap (Priority Queue)Counting

Reorganize String

Practise with tests LeetCode

1 approach, code in every language

Given a string s, reorder its characters so that no two adjacent characters are the same.

Return any valid rearrangement. If it is not possible to arrange the characters this way, return an empty string.

Example 1

Input: s = "aab"

Output: "aba"

Placing the two a's at positions 0 and 2 keeps them from touching.

Example 2

Input: s = "aaab"

Output: ""

Three a's cannot all be separated inside a four-character string, so no valid arrangement exists.

Constraints

1 <= s.length <= 500
s consists of lowercase English letters.

Frequency Count with Even/Odd Placement

Place the most frequent characters at even indices first, then wrap to the odd indices.

Loading animation…

Intuition

A valid arrangement exists exactly when no character appears more than ceil(n / 2) times, because that character can occupy at most every other position. Once that check passes, we can build the answer deterministically. Filling positions 0, 2, 4, ... with the most frequent character and continuing with the remaining characters guarantees that any two equal characters land at least two indices apart. When the even indices run out we wrap to index 1 and keep stepping by two through the odd indices. Because we always advance by two, adjacent cells are populated from different runs and never match.

Algorithm walkthrough

1Count the frequency of each character and identify the most frequent one.
2If that maximum frequency exceeds (n + 1) / 2, return an empty string because separation is impossible.
3Create a result buffer and start an index at 0, stepping by two through the even positions.
4Place every copy of the most frequent character first, then continue with the remaining characters.
5When the index passes the end of the buffer, reset it to 1 so it walks the odd positions.
6Join the buffer and return it; equal characters are guaranteed to be two positions apart.

Implementation

from collections import Counter

class Solution:
    def reorganizeString(self, s: str) -> str:
        counts = Counter(s)
        n = len(s)
        max_char, max_freq = counts.most_common(1)[0]
        if max_freq > (n + 1) // 2:
            return ""
        result = [""] * n
        idx = 0
        for ch, cnt in counts.most_common():
            for _ in range(cnt):
                if idx >= n:
                    idx = 1
                result[idx] = ch
                idx += 2
        return "".join(result)

Time

O(N)

Space

O(N)

Counting and placing each of the N characters is linear; the frequency table is a constant 26 slots and the result buffer holds N characters.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Priority Queues

After the pattern

Now solve one you haven't seen.

Paint Line Shuffle is our own problem on the technique behind Reorganize String: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free