Problem statement

https://binarysearch.com/problems/Unique-Characters-of-Every-Substring/

Solution

Equal to Leetcode 0828 Count Unique Characters of All Substrings of a Given String.

Complexity

Time and space complexity is O(n).

Code

class Solution:
    def solve(self, s):
        positions = defaultdict(list)
        n, ans = len(s), 0
        for i, elem in enumerate(s):
            positions[elem].append(i)
            
        for letter, pos in positions.items():
            diffs = list(x-y for x,y in zip(pos + [n], [-1] + pos))
            ans += sum(x*y for x,y in zip(diffs[1:], diffs[:-1]))
            
        return ans % (10**9 + 7)