贡献法:
# 贡献法:
# 首先我要批评我一个缺点就是:读题老是不仔细,为什么这么说呢,就是开始你以为的子串是原字符串中任意选几个字符出来构成的串,但是显然题目的意思不是这样的呀
# 题目中明显有 S[i....j]明显就是原字符串中连续的一段,连续的一段让题目好办一些
# 然后只要 某一个字母他 和其他人不一样(有一样的就没有贡献了哦),然后是连续的一段,不管长度多少,都可以贡献1
# 因此这样就简答啦
s=input().strip()
l=len(s)
A=[[-1] for i in range(26)]
for i in range(l):
x=ord(s[i])-ord('a') #都是由小写字母构成哦
A[x].append(i)
for i in range(26):
A[i].append(l) #增加-1和n这两个哨兵有利于计算哦
# 开始计算贡献
# 加入某一个字符串为 a xx a xxx a(其中x和a都互不相同),其中三个a的下标分别为(i,j,k)
# 前面可以产生的字符串有( xxa xa a),后面可以产生的字符串有 ( 0 0x 0xx 0xxx)
# 其中0表示空字符,因此总共的贡献值为 (j-i)*(k-j)
ans=0
for i in range(26):
L=len(A[i])
for j in range(1,L-1):
ans+=(A[i][j]-A[i][j-1])*(A[i][j+1]-A[i][j])
print(ans)
dp法:
# 这个也尝试一下用dp来做
s=input().strip()
l=len(s)
dp=[0 for i in range(l+1)]
loc=[0 for i in range(26)] #最先出现的字符的位置
roc=[0 for i in range(26)] #倒数第二个出现的位置
ans=0
for i in range(l):
x=ord(s[i])-ord('a')
dp[i+1]=dp[i]+(i+1-loc[x])-(loc[x]-roc[x])
roc[x]=loc[x]
loc[x]=i+1
ans+=dp[i+1]
print(ans)