字串分值和（Python-AC）

解题思路:

这题如果暴力遍历（O（n*n）），超时是肯定的

由于必须遍历数组，所以只能在O（n）的基础上做一些操作

思路：

遍历‘a’-‘z’，找出s中每一个字母能做的最大贡献，换句话说就是单看一个字母能存在于多少个字符串中 并且能计数
由于忽略重复性，对于单个字母的贡献可以从上一个字母的下标一直到字符串尾

s = input()
c = 'a'
ans = 0
while ord(c)<=ord('z'):
    if c in s:
        li = [-1]
        for i in range(len(s)):
            if c==s[i]:
                li.append(i)
        li.append(len(s))
        for i in range(1, len(li)):
            ans += (li[i]-li[i-1])*(li[-1]-li[i])
    c = chr(ord(c)+1)
print(ans)

注意事项:

参考代码: