Reorganize String
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.
Examples
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.
Constraints
- -1 <= s.length <= 500
- -s consists of lowercase English letters
Optimal Complexity
Time
O(n)
Space
O(1)
Practice this problem with an AI interviewer
TechInView conducts a full voice mock interview — the AI asks clarifying questions, evaluates your approach, watches you code, and scores you on 5 dimensions. Just like a real FAANG interview.
Start a free interview