Rearrange String to Avoid Adjacent Duplicates

Given a string S consisting of lowercase alphabets, determine if it is possible to rearrange the characters so that no two identical characters are adjacent. In other words, can we rearrange S into a string T where for all i, the condition T[i] ≠ T[i+1] holds?

You may consider a greedy approach: count the frequency of each character and try to place the most frequent characters first without causing two adjacent positions to be the same. A typical check is if the maximum frequency is no more than ⌊(n+1)/2⌋, where n is the length of the string, but you must simulate the rearrangement process to be sure.

inputFormat

The input is provided via standard input (stdin) as a single line containing the string S (only lowercase letters).

outputFormat

Output a single integer to standard output (stdout): output 1 if the string can be rearranged so that no two identical characters are adjacent; otherwise, output 0.

aab

1