找出该字符串中以不同字符开头和结尾的子串的数量

Question

找出该字符串中以不同字符开头和结尾的子字符串的数量。 如果同一个子串在S中出现多次，则要统计多次。

我应该遵循什么方法。我的解决方案没有优化

Answer 1

长度为

P=n*(n+1)/2

的字符串有

n

可能的子串（包括1长度的）

查找字符串中每个不同字符的计数。

banana => {'b':1; 'a':3; 'n':2}

如果某些字符

c

出现

k

次，则存在

k*(k+1)/2

子字符串以该字符

c

开头和结尾（再次包括 1 长度的子字符串！） - 所以我们必须从总体

P

中减去这个数量.
对其他字符重复此操作。

21 - 1 -6 - 3 = 11

如果子串长度应该>=2，那么我们必须使用

P=n*(n-1)/2

和

k*(k-1)/2

公式

15  -0 -3 -1 = 11

令人惊讶的是，结果是一样的;)