Valid Rearrangement of Characters

You are given a string s consisting of lowercase English letters. Your task is to determine whether it is possible to rearrange the characters of s such that no two adjacent characters are the same.

Formally, let the length of s be \(n\). A rearrangement is valid if for every \(1 \le i < n\), the \(i\)th character and the \(i+1\)th character are different. It can be shown that a valid rearrangement exists if and only if the frequency of the most frequent character is at most \(\lceil\frac{n}{2}\rceil\).

Output 1 if a valid rearrangement exists, otherwise output 0.

inputFormat

The input consists of a single line containing a non-empty string s composed of lowercase English letters only.

outputFormat

Output a single integer: 1 if there exists at least one rearrangement of s such that no two adjacent characters are the same; otherwise, output 0.

aabb

1