题目描述

对于一个字符串，如果其中存在某一个字母只出现过一次，则称这个字符串为“坏子串”。例如，abb、bcdde 是坏子串，而 aa、abcacb 不是坏子串。

给定一个仅由小写字母组成的字符串，请求出它有多少个子串是坏子串。

输入格式

一行，一个仅由小写字母组成的字符串。

输出格式

一行，一个整数，表示坏子串的数量。

样例

abba

8

样例解释

字符串 abba 的坏子串共有 $8$ 个，分别为：
a、ab、abb、b、bba、b、ba、a。

数据范围与提示

• 对于测试点 $1 \sim 4$：字符串长度不超过 $200$；
• 对于测试点 $5 \sim 8$：字符串长度不超过 $2000$；
• 对于测试点 $9 \sim 10$：字符串长度不超过 $10^5$，且字符种类数不超过 $2$；
• 对于测试点 $11 \sim 12$：字符串长度不超过 $10^5$；
• 对于测试点 $13 \sim 14$：字符串字符种类数不超过 $2$；
• 对于测试点 $15 \sim 20$：字符串长度不超过 $5 \times 10^6$。

字符串仅由小写英文字母组成。