828. Count Unique Characters of All Substrings of a Given String

class Solution:
    def uniqueLetterString(self, s: str) -> int:
        """ tc O(N)  sc O(N)  two rounds
        main idea: check left and right position, cnt = (cur-leftPos) * (rightPos - cur)
        1. for each char, save all the index appeared in the s 
        2. loop through all the charector, loop through all the index and get it's left and right position 
        3. Add count onto res with mode  
        """
        
        d = collections.defaultdict(list)
        for i,c in enumerate(s):
            d[c].append(i)
        
        res = 0
        for each in d.keys():
            #size = len(d[each])
            lst = d[each]
            for idx, cur in enumerate(lst):
                leftPos = lst[idx - 1] if idx != 0 else -1
                rightPos = lst[idx + 1] if idx != len(lst)-1 else len(s)
                res = res + (cur-leftPos) *(rightPos - cur)
        return res 

class Solution:
    def uniqueLetterString(self, s: str) -> int:
        """ tc O(N)  sc O(1) one rounds
        main idea: save last two appeared index for current char to save space
        """
        
        d = {c:[-1,-1] for c in string.ascii_uppercase}
        res = 0 
        for i,c in enumerate(s):
            fst, snd = d[c]
            res = res + (snd-fst) * (i-snd)
            d[c] = [snd,i] 
            
        for each in d.keys():
            fst, snd  = d[each]
            res = res + (snd-fst) *(len(s)-snd)
        return res