โ† Salesforce questions

Rearrange characters in a string without adjacent duplicates

Filed under Salesforce

Free read 3 of 3

Confirm 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

  1. Confirm what should be returned if rearrangement is impossible (empty string).

Solution

O(N log K) time where K is alphabet size, O(N) space

Python
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.