Reorganize String

I burned 35 minutes on this in a Stripe onsite, and the lesson I took away is that the impossibility check is half the problem. The greedy that uses a max-heap is the polished answer, but if you skip the upfront feasibility check (maxFreq <= (n + 1) / 2), you end up writing a heap-driven loop that quietly violates the constraint at the boundary. The catalog covers Task Scheduler (the same shape on a cooling cycle), but it skipped this string variant.

Reorganize String

Given a string s, rearrange the characters of s so that any two adjacent characters are NOT the same. Return any possible rearrangement of s or return "" if not possible.

Examples

Example 1:

• Input: s = "aab"
• Output: "aba" (any other valid rearrangement is also acceptable)
• Explanation: No two adjacent characters are equal.

Example 2:

• Input: s = "aaab"
• Output: ""
• Explanation: 3 as and 1 b. The as force adjacency.

Example 3:

• Input: s = "vvvlo"
• Output: "vlvov" (or any other valid rearrangement)
• Explanation: 3 vs, 1 l, 1 o. Place a v, then any other letter, then a v, etc.

Example 4:

• Input: s = "a"
• Output: "a"
• Explanation: Single-character strings are trivially valid.

Constraints

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

Follow-up

Feasibility test: a rearrangement exists iff the maximum frequency maxFreq satisfies maxFreq <= (n + 1) / 2 (integer division), where n is the string length. Why? The most frequent character must occupy at least one of every two consecutive slots; with n slots, that bounds it at ceil(n / 2) = (n + 1) / 2.