Problem statement

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

Solution

Let us inverse this problem and do it in the following way: for every symbol we will count number of substrings, for which it is unique. For example for word LEETCODE for symbol E we have positions 1, 2, 7. What we need to do: add also positions -1 and n here, where n is length of string, so we have -1,1, 2, 7, 8 now, evaluate differences between adjacent elements: 2, 1, 5, 1 and now evaluate sum of products of adjacent elements: 2 x 1 + 1 x 5 + 5 x 1 = 12. Why so? Because for each index we can go several place to the left and several places to the right.

Complexity

Time complexity is O(n), because we deal with each index only once, space complexity is O(n) as well.

Code

class Solution:
    def uniqueLetterString(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)