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.

Source: leetcode | Difficulty: MEDIUM
Tags: String algorithms

Dynamic programming

Data structures

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)
			for i in range(1, loc_ct - 1):
				leftWingSpan = locs[i] - locs[i - 1]
				rightWingSpan = locs[i + 1] - locs[i]
				ct += leftWingSpan % md * (rightWingSpan % md) % md
				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):
		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


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:
		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:

		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):
			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