Let's define a function countUniqueChars(s) that returns the number of unique characters on s, for example if s = "LEETCODE" then "L", "T","C","O","D" are the unique characters since they appear only once in s, therefore countUniqueChars(s) = 5.

On this problem given a string s we need to return the sum of countUniqueChars(t) where t is a substring of s. Notice that some substrings can be repeated so on this case you have to count the repeated ones too.
Since the answer can be very large, return the answer modulo 10 ^ 9 + 7.
 
Example 1:
Input: s = "ABC"
Output: 10
Explanation: All possible substrings are: "A","B","C","AB","BC" and "ABC".
Evey substring is composed with only unique letters.
Sum of lengths of all substring is 1 + 1 + 1 + 2 + 2 + 3 = 10

Example 2:
Input: s = "ABA"
Output: 8
Explanation: The same as example 1, except countUniqueChars("ABA") = 1.

Example 3:
Input: s = "LEETCODE"
Output: 92

 
Constraints:

0 <= s.length <= 10^4
s contain upper-case English letters only.

Difficulty: interview

Starter code:

class Solution:
    def uniqueLetterString(self, s: str) -> int:
        

Solutions:
class Solution:
    def uniqueLetterString(self, s: str) -> int:
        chrLoc = defaultdict(list)
        ct = 0
        md = 1000000007
        l = len(s)
        for i, c in enumerate(s):
            chrLoc[c].append(i)
        
        for c in chrLoc:
            locs = [-1] + chrLoc[c] + [l]
            loc_ct = len(locs)
            #print(c, locs)
            for i in range(1, loc_ct-1): 
                leftWingSpan = locs[i] - locs[i-1] #i-mostRecently + 1
                rightWingSpan = locs[i+1] - locs[i]  # l-i
                ct += ((leftWingSpan % md) * (rightWingSpan % md)) % md
                #print(leftWingSpan,rightWingSpan, c, i)
                ct %= md 
                
        return ct

class Solution:
    def uniqueLetterString(self, s: str) -> int:
        dic = {}
        for i in range(len(s)):
            l = dic.get(s[i],[-1])
            l.append(i)
            dic[s[i]] =l
        res = 0
        for j in dic:
            dic[j].append(len(s))
            for i in range(1, len(dic[j])-1):
                res+= (dic[j][i] - dic[j][i-1])*(dic[j][i+1]-dic[j][i])
        return res%(10**9+7)

class Solution:
    def uniqueLetterString(self, s: str) -> int:
        if not s:
            return 0
        
        ind = defaultdict(list)
        for i, ch in enumerate(s):
            ind[ch].append(i)
        
        res = 0
        for seq in ind.values():
            for i, index in enumerate(seq):
                len_left, len_right = 0, 0
                if i > 0:
                    len_left = index - seq[i - 1] - 1
                else:
                    len_left = index
                
                if i + 1 < len(seq):
                    len_right = seq[i + 1] - index - 1
                else:
                    len_right = len(s) - index - 1
                
                res += ((len_left + 1) * (len_right + 1))
        
        return res

class Solution:
    def uniqueLetterString(self, s: str) -> int:
        n = len(s)
        dbefore = {}
        dafter = {}
        before = [-1] * n
        after = [n] * n
        for i in range(n):
            before[i] = dbefore.get(s[i], -1)
            after[n-1-i] = dafter.get(s[n-1-i], n)
            dbefore[s[i]] = i
            dafter[s[n-1-i]] = n-1-i
        c = 10 ** 9 + 7
        res = 0
        for i in range(n):
            res += (i-before[i])*(after[i]-i)
            res %= c
        return res

# from collections import defaultdict
# class Solution(object):
#     def uniqueLetterString(self, s):
#         \"\"\"
#         :type S: str
#         :rtype: int
#         \"\"\"
#         dic = defaultdict(list)
#         for i,letter in enumerate(s):
#             dic[letter].append(i)
        
#         pos = {letter:0 for letter in dic.keys()}
#         res = 0
#         for i,letter in enumerate(s):
#             idx = pos[letter]
            
#             if idx - 1 >= 0:
#                 left = dic[letter][idx - 1] + 1
#             else:
#                 left = 0
#             if idx + 1 <= len(dic[letter]) - 1:
#                 right = dic[letter][idx + 1] - 1
#             else:
#                 right = len(s) - 1
            
#             res += (i - left + 1) * (right - i + 1)
#             pos[letter] += 1
        
#         return res % (10 ** 9 +7)
from collections import defaultdict
class Solution(object):
    def uniqueLetterString(self,S):
        # write your code in Python 3.6
        dictionary = dict()

        for i in range(len(S)):
            if dictionary.get(S[i]):
                dictionary[S[i]].append(i)
            else:
                dictionary[S[i]] = [i]
        position = dict()
        for letter in dictionary.keys():
            position[letter]=0
        result = 0
        for index, letter in enumerate(S):
            i = position[letter]
            if i-1>=0:
                l = dictionary[letter][i-1]+1
            else:
                l=0
            if i+1 <= len(dictionary[letter])-1:
                r = dictionary[letter][i+1]-1
            else:
                r = len(S) - 1

            result += ((index-l+1) * (r-index +1)) % 1000000007
            position[letter]+=1
        return result % 1000000007

class Solution:
    def uniqueLetterString(self, s: str) -> int:
        ans, d = 0, defaultdict(lambda: (-1, -1))
        for i, c in enumerate(s):
            ans += (d[c][1]-d[c][0])*(i-d[c][1])
            d[c] = (d[c][1], i)
        for c, pre in d.items():
            ans += (d[c][1]-d[c][0])*(len(s)-d[c][1])
        return ans

# from collections import defaultdict
# class Solution(object):
#     def uniqueLetterString(self, s):
#         \"\"\"
#         :type S: str
#         :rtype: int
#         \"\"\"
#         dic = defaultdict(list)
#         for i,letter in enumerate(s):
#             dic[letter].append(i)
        
#         pos = {letter:0 for letter in dic.keys()}
#         res = 0
#         for i,letter in enumerate(s):
#             idx = pos[letter]
            
#             if idx - 1 >= 0:
#                 left = dic[letter][idx - 1] + 1
#             else:
#                 left = 0
#             if idx + 1 <= len(dic[letter]) - 1:
#                 right = dic[letter][idx + 1] - 1
#             else:
#                 right = len(s) - 1
            
#             res += (i - left + 1) * (right - i + 1)
#             pos[letter] += 1
        
#         return res % (10 ** 9 +7)
from collections import defaultdict
class Solution(object):
    def uniqueLetterString(self,S):
        # write your code in Python 3.6
        dictionary = dict()
    
        for i in range(len(S)):
            if dictionary.get(S[i]):
                dictionary[S[i]].append(i)
            else:
                dictionary[S[i]] = [i]
        position = dict()
        for letter in dictionary.keys():
            position[letter]=0
        result = 0
        for index, letter in enumerate(S):
            i = position[letter]
            if i-1>=0:
                l = dictionary[letter][i-1]+1
            else:
                l=0
            if i+1 <= len(dictionary[letter])-1:
                r = dictionary[letter][i+1]-1
            else:
                r = len(S) - 1

            result += ((index-l+1) * (r-index +1)) % 1000000007
            position[letter]+=1
        return result % 1000000007

class Solution:
    
    

    
    def uniqueLetterString(self, s: str) -> int:
        result = 0
        mat = collections.defaultdict(list)
        for i, ch in enumerate(s):
            if mat[ch]:
                mat[ch].append(i)
            else:
                mat[ch] = [i]
                
        def helperF(ranges, n):
            res = 0
            i = 0
            while i < len(ranges):
                elem = ranges[i]
                lef = None
                right = None
                if i > 0:
                    left = ranges[i] - ranges[i - 1]
                else:
                    left = ranges[i] + 1
                if i != len(ranges) - 1:
                    right = ranges[i + 1] - ranges[i]
                else:
                    right = n - ranges[i]
                res += left * right
                i += 1
            return res
                
                
        for ch in mat:
            result += helperF(mat[ch], len(s))
        return result

class Solution:
    def uniqueLetterString(self, s: str) -> int:
        
        ind = collections.defaultdict(list)
        for i,v in enumerate(s): ind[v].append(i)
        
        ans , n = 0, len(s)
        for i,v in ind.items():
            temp = 0
            for k,index in enumerate(v):
                if k==0 and k==len(v)-1: 
                    temp+=(index+1)*(n-index)
                elif k==0: 
                    temp+=(index+1)*(v[k+1]-index)
                elif k>0 and k<len(v)-1: 
                    temp+=(index-v[k-1])*(v[k+1]-index)
                elif k==len(v)-1: 
                    temp+=(index-v[k-1])*(n-index)
            ans+=temp
        
        return ans

class Solution:
    def uniqueLetterString(self, s: str) -> int:
        
        ind = collections.defaultdict(list)
        for i,v in enumerate(s): ind[v].append(i)
        
        ans , n = 0, len(s)
        for i,v in ind.items():
            temp = 0
            # print(i,v, temp)
            for k,index in enumerate(v):
                if k==0 and k==len(v)-1: 
                    temp+=(index+1)*(n-index)
                elif k==0: 
                    temp+=(index+1)*(v[k+1]-index)
                elif k>0 and k<len(v)-1: 
                    temp+=(index-v[k-1])*(v[k+1]-index)
                elif k==len(v)-1: 
                    temp+=(index-v[k-1])*(n-index)
                # print(k,index,temp)
            ans+=temp
            # print('-----------------------')
        
        return ans

class Solution:
    def uniqueLetterString(self, s: str) -> int:
        n = len(s)
        mod = 10**9+7
        index = defaultdict(deque)
        for i,c in enumerate(s):
            index[c].append(i)
        for c in index:
            index[c].append(n)
            index[c].appendleft(-1)
        ans = 0
        for c in list(index.keys()):
            for i in range(1,len(index[c])-1):
                ans = (ans + (index[c][i]-index[c][i-1]) * (index[c][i+1]-index[c][i])) % mod
                
        return ans


class Solution:
    def uniqueLetterString(self, s: str) -> int:
        '''
        For each 'char' in string, count the number of substrings contains this 'char' and only one 'char'.
        Time: O(n)
        Space: O(n)
        '''
        def count(c, s):
            n = len(s)
            idxes = []
            for i in range(n):
                if s[i] == c:
                    idxes.append(i)
            total = 0
            for i, idx in enumerate(idxes):
                left = idx - 0 + 1
                right = n - 1 - idx + 1
                if i:
                    left = idx - idxes[i-1]
                if i < len(idxes) - 1:
                    right = idxes[i+1] - idx
                total += left * right
            return total
        
        chars = set(s)
        ans = 0
        for c in chars:
            ans += count(c, s)
            ans = ans % (10 ** 9 + 7)
        return ans

class Solution:
    def uniqueLetterString(self, s: str) -> int:
        index = {char:[-1]+[ic for ic,char0 in enumerate(s) if char == char0]+[len(s)] for char in set(s)}
        return sum([(index[char][jj]-index[char][jj-1])*(index[char][jj+1]-index[char][jj]) for char in index for jj in range(1,len(index[char])-1)])

class Solution:
    def uniqueLetterString(self, s: str) -> int:
        
        last = collections.defaultdict(int)
        count = 0
        for i, char in enumerate(s):
            # print(last)
            for comp in last:
                if comp != char:
                    count +=  last[comp][1] 
                else:
                    count += i-last[comp][0]
                    last[char] = (i, i-last[comp][0])
            if char not in last:
                count += i+1
                last[char] = (i, i+1)
        return count
                
            
                
            
            


class Solution:
    def uniqueLetterString(self, s: str) -> int:
        if not s: return 0
        
        dp = collections.defaultdict(list)
        for index, val in enumerate(s):
            dp[val].append(index)
        
        ans = 0
        for A in list(dp.values()):
            A = [-1] + A + [len(s)]
            
            for i in range(1, len(A)-1):
                ans += (A[i] - A[i-1]) * (A[i+1]-A[i])
                
        return ans % (10**9 + 7)


class Solution:
    def uniqueLetterString(self, s: str) -> int:
        index = collections.defaultdict(list)
        for i, c in enumerate(s):
            index[c].append(i)
        
        ans = 0
        for a in index.values():
            a = [-1] + a + [len(s)]
            for i in range(1, len(a) - 1):
                ans += (a[i] - a[i-1]) * (a[i+1] - a[i])
        return ans % (10**9 + 7)

class Solution:
    def uniqueLetterString(self, s: str) -> int:
        dic=collections.defaultdict(list)
        for i ,e in enumerate(s):
            dic[e].append(i)
            
        for k in dic.keys():
            dic[k].append(len(s))
            dic[k].insert(0,-1)
            
        res=0
        for v in dic.values():
            for i in range(1,len(v)-1):
                res+=((v[i]-v[i-1])*(v[i+1]-v[i]))%(10**9+7)
                
        return res

class Solution:
    def uniqueLetterString(self, s: str) -> int:
        mod = 1000000007
    
        n = len(s)

        char_locs = defaultdict(list)
        for i in range(n):
            c = s[i]
            if not char_locs[c]: char_locs[c].append(-1)
            char_locs[c].append(i)


        ans = 0  
        for c in char_locs:
            char_locs[c].append(n)
            indices = char_locs[c]

            for i in range(1, len(indices)-1):
                before = indices[i] - indices[i-1]
                after = indices[i+1] - indices[i]

                ans = (ans + before*after) % mod

        return ans