[LeetCode] 828. Count Unique Characters of All Substrings of a Given String

 Problem : https://leetcode.com/problems/count-unique-characters-of-all-substrings-of-a-given-string/

Instead of counting substrings, count the contribution of each unique character.

class Solution:
    def uniqueLetterString(self, s: str) -> int:
        N = len(s)
        
        seen = defaultdict(lambda: -1)
        left = [0] * N   # the left side window in which the ith character is unique
        
        for i in range(N):
            left[i] = seen[s[i]]
            seen[s[i]] = i
        
        seen = defaultdict(lambda: N)
        right = [0] * N  # the right side window in which the ith character is unique
        
        for i in reversed(range(N)):
            right[i] = seen[s[i]]
            seen[s[i]] = i
        
        
        result = 0
        
        for i in range(N):
            # ith character can be unique in (left window size) * (right window size) substrings. 
            result += (i - left[i]) * (right[i] -i)
        
        return result