本蒟蒻求dalao给个思路qwq

实在是搜不到想不出来了

题目描述

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

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

输入文件 badstring.in

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

输出文件 badstring.out

输出一个整数表示答案。

输入数据1

abba

输出数据 1

8

样例解释

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

对于 1 ∼ 4 测试点，保证字符串长度不超过 200

对于 5 ∼ 8 测试点，保证字符串长度不超过 2000。

对于 9 ∼ 10 测试点，保证字符串长度不超过 $10^5$ 且字符种类数不超过 2。

对于 11 ∼ 12 测试点，保证字符串长度不超过 $10^5$ 。

对于 13 ∼ 14 测试点，保证字符串的字符种类不超过 2 。

对于 15 ∼ 20 15∼20 测试点，保证字符串长度不超过 5 × $10^6$