题目描述

对于一个字符串，我们认为这个字符串中出现次数最多的字符所出现的次数，与出现次数最少的字符所出现次数的差值，称为该字符串的频差，以此来量化这个字符串中字符出现的频率是否均匀。

例如，字符串 s='helloworld'，出现次数最多的字符是l，出现了 $3$ 次，出现次数最多的字符是h，出现了 $1$ 次，因此我们认为这个字符串的频差为 $2$。

现给定一个字符串$s$，请问其所有子串的频差中，最大频差为多少？

输入格式

输入共一行，一个字符串$s$

输出格式

输出共一行，一个正整数表示答案

aiiai

2

样例解释 1

选择子串为iiai，子串的频差最大，为3-1=2

数据范围

• 对于$30\%$的数据，$1 \leq |s| \leq 100$
• 对于$60\%$的数据，$1 \leq |s| \leq 10^4$
• 对于$100\%$的数据，$1 \leq |s| \leq 5 \times 10^5$

式中$|s|$表示字符串$s$的长度