Rearrange String to Avoid Adjacent Duplicates

You are given a string s consisting of lowercase English letters. Your task is to rearrange the characters of s so that no two adjacent characters are the same. If such a rearrangement is possible, output the rearranged string; otherwise, output NO.

The solution should use a greedy algorithm (often implemented with a max‐heap) to always pick the character with the highest remaining count which is not the same as the previously placed character. If the rearrangement cannot be completed successfully, print NO.

For example:

• Input: aabb → Output: abab
• Input: aaab → Output: NO
• Input: a → Output: a

inputFormat

Input is given via stdin as a single line containing a string s consisting only of lowercase English letters.

outputFormat

Output the rearranged string (via stdout) such that no two adjacent characters are the same. If it is impossible to rearrange s accordingly, output NO.

aabb

abab