1907：蒜头君组回文串
文件提交：无需freopen
内存限制：128 MB
时间限制：1.000 S
评测方式：普通裁判
命题人：
提交：2
解决：2
题目描述
蒜头君收到了一条 非空的字符串 。
一个 非空字符串 ，如果从左到右和从右到左读取时都是相同的，被称为回文字符串。例如，字符串`abcba`、`a`和`abba`是回文字符串，而`abab`和`xy`则不是。
而同时，一个字符串被称为另一个字符串的子串，如果它可以通过从该字符串的开头和结尾删除一些（可能为零）字符来获得。例如，`abc`、`ab`和`c`是字符串`abc`的子串，而`ac`和`d`则不是。
蒜头君对于字符串的回文性质十分痴迷，因此，对于一个字符串，他定义了一个叫做`回文度`的概念：一个字符串的回文度是指字符串中有多少个非空子串是回文字符串。
现在，蒜头君希望你对他收到的字符串重新调整字符顺序，使得新字符串的回文度最大。
一个 非空字符串 ，如果从左到右和从右到左读取时都是相同的，被称为回文字符串。例如，字符串`abcba`、`a`和`abba`是回文字符串，而`abab`和`xy`则不是。
而同时，一个字符串被称为另一个字符串的子串，如果它可以通过从该字符串的开头和结尾删除一些（可能为零）字符来获得。例如，`abc`、`ab`和`c`是字符串`abc`的子串，而`ac`和`d`则不是。
蒜头君对于字符串的回文性质十分痴迷，因此，对于一个字符串，他定义了一个叫做`回文度`的概念：一个字符串的回文度是指字符串中有多少个非空子串是回文字符串。
现在，蒜头君希望你对他收到的字符串重新调整字符顺序，使得新字符串的回文度最大。
输入
输入共一行，仅由小写英文字母组成，代表蒜头君收到的字符串。
设字符串长度为 $n(1\le n\le 5\times 10^5)$
输出
输出一个正整数，代表最后蒜头君对收到的字符串重新调整字符顺序后可以达到的最大的回文度。
样例输入-1 复制
gagadbcgghhchbdf样例输出-1 复制
29样例输入-2 复制
aqq样例输出-2 复制
4提示
样例解释1：一种可能的重排后的字符串为 abccbaghghghgdfd，此时的回文长度为 $29$。所有的回文子字符串为: 'a','abcba','b','bccb','c','cc','c','b','a','g','ghg','ghghg','ghghghg',
'h','hgh','hghgh','g','ghg','ghghg','h','hgh','g','ghg','h','g','d','dfd','f','d'
样例解释2：一种可能的重排后的字符串为 qaq，此时回文长度为 $4$。所有的回文子字符串为: 'q','a','q','qaq'
