Example 3: What is the output for input s = "aabb"?

Output: "abab". We can alternate the characters: "abab" or "baba" are both valid.

MediumHeap

Reorganize String

Output: "aba". We can rearrange "aab" to "aba" where no two adjacent characters are the same.

Output: "". It is not possible to rearrange the string so that no two adjacent characters are the same.

googleamazonmetamicrosoftbloombergappleuber

Given a string s, rearrange the characters of s so that any two adjacent characters are not the same.

Return any valid rearrangement of s, or return "" if not possible.

Example 1:

Input: s = "aab"
Output: "aba"
Explanation: We can rearrange "aab" to "aba" where no two adjacent characters are the same.

Example 2:

Input: s = "aaab"
Output: ""
Explanation: It is not possible to rearrange "aaab" so that no two adjacent characters are the same.

Example 1

Input: s = "aab"

Output: "aba"

Explanation: We can rearrange "aab" to "aba" where no two adjacent characters are the same.

Example 2

Input: s = "aaab"

Output: ""

Explanation: It is not possible to rearrange the string so that no two adjacent characters are the same.

Example 3

Input: s = "aabb"

Output: "abab"

Explanation: We can alternate the characters: "abab" or "baba" are both valid.

Time

O(n)

Space

O(1)

One problem, two ways to prep

Practice Mode keeps things simple with code + tests. AI Interview Mode adds voice, pressure, and a post-round score summary.