题解-统计子串中的唯一字符-哈希表+栈，计算贡献

Problem: 828. 统计子串中的唯一字符

思路

• 注意到一个唯一字符对数个子串生效，也就是在多个子串中唯一字符是固定的那几个，很容易想到贡献法
• 对于子串起点和终点我们设置成$left,right$,任意字符位置为$a_i$序列,让子串生效的范围是$left-right$这个范围内,存在一个字符a,其序列满足
  $$a_{i-1}<left<=a_i<=right<a_{i+1}$$,
• 同样可以通过枚举起点终点,得知满足这个条件子串的个数为 $(a_i-a_{i-1})*(a_{i+1}-a_{i})$,
• 为了计算方便我们将-1和n作为每个字符的两端,既$a_{-1}=-1,a_{n+1}=n$
• 该字母在$a_i$上为答案做的贡献就等于子串的数量

解题方法

• 使用哈希表存储每个字母的位置序列
• 为了前后方便我们使用栈来维护具体的字母序列

时间复杂度,O(n)
空间复杂度,O(n)

Code

class Solution:
    def uniqueLetterString(self, s: str) -> int:
        n=len(s) 
        hash=[[n] for _ in range(26)] #最右端点
        for i in range(len(s)-1,-1,-1):
            hash[ord(s[i])-ord('A')].append(i)
            #小的在顶部,大的在底部
        res=0
        for i in range(26):
            pre=-1
            while len(hash[i])>1:
                index=hash[i].pop()
                back=hash[i][-1]
                res+=(index-pre)*(back-index)
                pre=index
        return res