AcWing 2868. 子串分值
原题链接
中等
作者:
曦薇
,
2022-04-05 22:32:12
,
所有人可见
,
阅读 197
思路
- 思考在字符串 $s$ 中的 $s[i]$ 对答案的贡献:假设有 $l < i$ 且 $s[l]=s[i]$ 且$(l,i)$ 内的字符均不等于 $s[i]$ ; 有 $r>i$ 且 $s[r]=s[i]$ 且 $(i,r)$ 内的字符均不等于 $s[i]$ ;即在 $(l,r)$ 内有且仅有一个 $s[i]$ 字符,则包含 $s[i]$ 的任意一个子区间中 $s[i]$ 对答案均有 $1$ 的贡献,这些子区间的数量为 $(i-l)\times(r-i)$ 。注意对字符进行统计时需要加上左右边界。
- 按照上面的思路,先处理出来字符的索引,然后遍历索引更新答案。
- 时间复杂度为 $O(n)$ ,空间复杂度为 $O(n)$ 。
AC代码(python)
if __name__ == '__main__':
s=list(input().strip())
s.insert(0,0)
ans=0
l=[[0] for i in range(26)]
for i in range(1,len(s)):
a=ord(s[i])-ord('a')
l[a].append(i)
for i in range(26):
l[i].append(len(s))
for i in range(26):
for j in range(1,len(l[i])-1):
x1=l[i][j]-l[i][j-1]
x2=l[i][j+1]-l[i][j]
ans+=x1*x2
print(ans)