Leetcode 828. Count Unique Characters of All Substrings of a Given String [Python]_code testcase test result test result 828. count u

题目反过来思考，对于一个字符，其为假设其前面没有与他类似的字符，例：xxx+A,增加的A为subarray：A，xA，xxA，xxxA，增加了4个unique letter（即A）。而如果我们在之前的某位上已经出现了A，假设为xxAxxxA，则增加的后一个A，可以为全部的xxAxxx增加的 unique letter，只出现在后部分，也就是xxxA上面，而从再往左增加一位后，A就不再是重复的了，所以，到第二个A出现时，整个xxAxxxA所能得到的unique letter就要减去第一个A出现时，得到的unique letter增加量。我们使用temp记录每次增加一个letter，可以得到的增量，其计算就为当前字符的位置减去其相同字符上次出现的位置，并减去由上一个相同的字符出现时，得到的unique letter增加量。我们把这个增量加到res中。

class Solution:
    def uniqueLetterString(self, s: str) -> int:
        res = 0
        anountandpos = [(0,-1) for _ in range(26)]
        
        temp = 0
        for i in range(len(s)):
            pos = ord(s[i]) - ord('A')
            prevamount, prepos = anountandpos[pos]
            temp += (i - prepos) - prevamount
            res += temp
            anountandpos[pos] = (i - prepos,i)
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13