题目描述

对于一个字符串而言，假设有某一个字母只出现过一次，那么我们就称它为 “坏子串”。 例如 “abb”，“bcdde” 就是坏子串，而 “aa”，“abcacb” 不是坏字符串。

给一个字符串，请问有多少个子串是坏子串。

输入文件 badstring.in

输入一个仅由小写字母组成的字符串。

输出文件 badstring.out

输出一个整数表示答案。

abba

8

“a”、“ab”、“abb”、“b”、“bba”、“b”、“ba”、“a” 共有 $8$ 个坏子串。

提示

样例 $2$ 见附加文件。

对于 $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 × 10^6$ 。