O(N), DP, Python, simple method
Inspired by https://leetcode.com/problems/total-appeal-of-a-string/discuss/1996203/DP. The general idea is to seperate all the subarries of string s into n grou
Inspired by https://leetcode.com/problems/total-appeal-of-a-string/discuss/1996203/DP. The general idea is to seperate all the subarries of string s into n groups, each contains subarries end at position i, 0<= i < n. And use dp method to get the answer.\n\nThis problem is similiar to problem 2262, that requests the sum of occured characters in subarrays -- including the duplicated ones, which has less constrains and is easier to understand. So we start from that:\n\nAssume we hava s = "ABA"\n(i = 0) A\n(i = 1) AB, B\n(i = 2) ABA, BA, A\n\nFor i = 0, the sum of number of charachters in all subarries is 1.\ni = 1, we have a new charachter B and 1 updated subarry "AB" from "A" and a new subarry "B". charachter B at i = 1 contributes to 1 for old subarry "A" and of course, 1 for the new subarry formed by itself.\ni = 2, A should contribute 1 for both "AB" and "B", however "ABA" counts for 2. So it only contribute to subarries **start after A**. So the answer for subarry ends at i consists of two parts: one is from subarry ends at i - 1, another is the number of subarraies start after last occurence of current charachter, dp[i] = dp[i - 1] + i - prev[s[i]]. *prev* is a map records the last occured position of each character, default is -1, and i - (-1) means current character contributes to all the previous subarries.\n\nThe code is like:\n ```\ndef solution(self, s: str)->int\n\tn = len(s)\n\tdp = [0] * n\n\tprev = defaultdict(lambda: -1)\n\tfor i in range(n):\n\t\t\tif i == 0:\n\t\t\t\t dp[i] = 1\n\t\t\telse:\n\t\t\t\tdp[i] = dp[i - 1] + i - prev[s[i]]\n\t\t\tprev[s[i]] = i\n\treturn sum(dp)\n ```\n\nThere are two more constrains in this problem that the charachter at position i in string s:\n1. contributes **-1** to subarries that s[i] occured **once**, which start after **last but second** occurrence position.\n2. has no affact to subarries with **2 more** occurrence, no need to calculate.\n\nSo the dp[i] is made of 3 parts:\n1. dp[i - 1]\n2. (1) * (i - prev[s[i]][-1])\n3.  (-1) * (prev[s[i]][-1] - prev[s[i]][-2])\n\nThis time we need a map for characters to their positions. And we don\'t need an extra array to keep the answers of all subarries since they are derived directly from last subarry. The code is like:\n\n```\ndef uniqueLetterString(self, s: str) -> int:\n    ans, curr, prev = 0, 0, defaultdict(list)\n    for i, ch in enumerate(s):\n        if len(prev[ch]) == 0: prev[ch].append(-1)\n        curr += (1 if i == 0 else i - prev[ch][-1])\n        if len(prev[ch]) > 1:\n            curr -= (prev[ch][-1] - prev[ch][-2])\n        prev[ch].append(i)\n        ans += curr\n    return ans\n```\n\t
['Dynamic Programming', 'Python']