Leetcode 2262. Total Appeal of A String [Python]

一眼看上去真不会，看了Hint，写出来了。
Hint的思路很详细，找一个index i，那包含某一个字母且截止于index i的substring的总数就是这个字母离index i最近出现的位置（假设为j，j <= i）j + 1。比如abc，在index i = 2处截止，含有c的substring数量，c，bc，abc，含有b的，b，ab， 含有a的a。所以，到此为止，截止于index i = 0处的全部substring，只有一个a；截止于index i = 1处的string的全部substring，a, ab, b. 也就包含b的2个加包含a的一个，截止于index i = 2处的string的全部substring，abc, bc, c，ab, b, a ; 因此设置dp数组，dp【i】代表截止于index i 处的string的全部substring。dp[i] = dp[i-1] + (i + 1), i+1指的是index i上出现的包含字母s【i】的substring，dp[i-1]是前面的susbstring的总数。但是 但是，如果某个字母在之前出现过了呢？比如abcb。index = 1和 index = 4上都是字母b，此时在index = 4处的substring是 abcb，bcb，cb， b以及 abc，bc，c和ab，b 还有a。此时的abcb，bcb，都重复了b，所以其实第二个b在这两个substring中并没有贡献，因为第一个b已经贡献过了，因此需要剪去重复计算的，重复的数量就是ab和b两个贡献了b的substring。也就是（index = 1） + 1。我们设置一个dict来记录每个字母出现的最新的位置。

class Solution:
    def appealSum(self, s: str) -> int:
        dp = [0]*len(s)
        dp[0] = 1
        haxi_map = collections.defaultdict(int)
        haxi_map[s[0]] = 0
        for i in range(1, len(s)):
            dp[i] = i + 1 + dp[i-1]
            
            if s[i] in haxi_map:
                dp[i] -= (haxi_map[s[i]] + 1)
            haxi_map[s[i]] = i
        #print(haxi_map)
        #print(dp)
        return sum(dp)