Rearrange characters in a string without adjacent duplicates
Filed under Salesforce
Free read 3 of 3Confirm what should be returned if rearrangement is impossible (empty string).
The question
Given a string, rearrange its characters such that no two identical characters are adjacent to each other. If valid rearrangement is not possible, return an empty string or special indicator.
Constraints
- 1 <= length of string <= 10^4
- String consists of lowercase English letters.
Examples
- Input
- s = "aab"
- Output
- "aba"
- Why
- 'a' and 'b' are rearranged so no identical characters are adjacent.
- Input
- s = "aaab"
- Output
- ""
- Why
- Character 'a' appears too many times (more than half + 1), making separation impossible.
Approach
Confirm what should be returned if rearrangement is impossible (empty string).
Generate all permutations and check each for adjacent duplicates. Unfeasible for lengths > 10.
Count frequencies of each character. Use a max-heap to always place the most frequent available character next, ensuring it is not the same as the previously placed character.
Strings with all identical characters, or where max frequency > (N+1)//2.
Solution
O(N log K) time where K is alphabet size, O(N) space
from collections import Counter
import heapq
class Solution:
def reorganizeString(self, s: str) -> str:
count = Counter(s)
pq = [(-cnt, char) for char, cnt in count.items()]
heapq.heapify(pq)
res = []
prev = (0, '')
while pq:
cnt, char = heapq.heappop(pq)
res.append(char)
if prev[0] < 0:
heapq.heappush(pq, prev)
prev = (cnt + 1, char)
result = "".join(res)
return result if len(result) == len(s) else ""
Tips
- What they are testing: Test with strings where one character dominates, strings with all distinct characters, and even/odd length inputs.
- Common mistake: Using a naive greedy approach without considering character frequency counts, leading to incorrect interleavings.
Related Salesforce questions
Collected from public candidate posts and coding forums. Updated Nov 2026.