DSA problem
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 an empty string "" if it is not possible.
A valid rearrangement exists if and only if no single character occurs more than (n + 1) / 2 times, where n is the length of the string. If the most frequent character exceeds that bound, it is impossible to separate all of its occurrences with other characters and you must return the empty string.
Examples
Example 1
Input:
s = "aab"Output:
"aba"Explanation: The character a appears twice and b appears once. Placing them as a, b, a leaves no two equal characters adjacent.
Example 2
Input:
s = "aaab"Output:
""Explanation: The character a appears 3 times out of length 4. Since 3 > (4 + 1) / 2 = 2, the as cannot all be separated, so no valid arrangement exists.
Example 3
Input:
s = "vvvlo"Output:
"vlvov"Explanation: v appears 3 times, which equals (5 + 1) / 2 = 3, so a valid arrangement like v, l, v, o, v exists.
Constraints
- 1 <= s.length <= 500
- s consists of lowercase English letters.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.