Rearrange String to Avoid Character Pair - Solution & Explanation

Problem Overview: You need to rearrange characters in a string so a restricted character pair does not appear next to each other. The challenge is preserving all characters while building a valid ordering. Most solutions rely on frequency tracking and careful placement of characters during iteration.

Approach 1: Generate All Permutations (O(n!))

The brute force approach generates every possible permutation of the string and checks whether the resulting arrangement contains the forbidden adjacent pair. You iterate through each permutation and validate neighboring characters with a simple scan. This approach is useful for understanding the constraint, but it becomes unusable once the string length grows beyond small test cases. Space complexity is O(n) for recursion and temporary storage.

Approach 2: Greedy Frequency Placement with Sorting (O(n log n))

A more practical method counts character frequencies using a hash map, sorts characters by frequency, then places them strategically to avoid invalid adjacency. The key insight is to distribute high-frequency characters first so they do not cluster into restricted pairs later. You repeatedly append a valid character while tracking the previously placed character and the restricted combination. This approach works well when the alphabet size is limited and is commonly implemented with arrays or hash maps. Time complexity is O(n log k), where k is the number of distinct characters, and space complexity is O(k).

Approach 3: Max Heap Greedy (O(n log k))

The optimal interview approach uses a max heap to always pick the character with the highest remaining frequency that does not violate the adjacency rule. You pop the best candidate, append it to the result, then temporarily hold the previously used character until it becomes valid again. This prevents invalid pairs while ensuring characters are consumed efficiently. Heap operations keep insertion and extraction fast, making this approach scalable for larger inputs. It combines greedy algorithms with priority queues. Time complexity is O(n log k) and space complexity is O(k).

Recommended for interviews: Interviewers typically expect the heap-based greedy solution because it demonstrates control over ordering constraints and efficient frequency management. Showing the brute force approach first proves you understand the problem definition, but moving to the heap optimization shows stronger algorithmic thinking and better scalability analysis.