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

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

• 思路
• 解题方法
• Code

思路

• 注意到一个唯一字符对数个子串生效，也就是在多个子串中唯一字符是固定的那几个，很容易想到贡献法

• 对于子串起点和终点我们设置成,任意字符位置为序列,让子串生效的范围是这个范围内,存在一个字符a,其序列满足
  ,

  • 同样可以通过枚举起点终点,得知满足这个条件子串的个数为

    ,

  • 为了计算方便我们将-1和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