Conditional Character Redistribution

You are given a string S consisting of lowercase English letters.

Allowed Operation:

You may perform at most one operation:

• Pick any one character

• Move it to any other position in the string

This operation is optional, so you may also choose not to perform it.

Goal:

After this, determine whether it is possible to rearrange the string such that:

• No two adjacent characters are the same

Return:

• "YES" if it is possible

• "NO" otherwise

📥 Input Format

• A single string S

📤 Output Format

• Return "YES" if the string can be rearranged so that no two adjacent characters are the same

• Otherwise return "NO"

⚙️ Constraints

• 1≤∣S∣≤1000001 \le |S| \le 1000001≤∣S∣≤100000

🧪 Examples

Example 1

Input:

aab

Output:

YES

Explanation: The string can be arranged as "aba" so no adjacent characters are the same.