Python O(N), with explanation
\n\nLet dp[i] = the total unique character end with s[i],\nLet\'s first consier an easy case, \nif each character is distinct, we have  dp[i] = dp[i-1] + i +1\n
\n\nLet dp[i] = the total unique character end with s[i],\nLet\'s first consier an easy case, \nif each character is distinct, we have  **dp[i] = dp[i-1] + i +1**\n\tdp[0] = 1\n\tdp[1] = dp[0] + 1 + 1\n\tdp[2] = dp[1] + 2 + 1\n\tdp[i] = dp[i-1] + i +1\n\tconsider the following case s = "ABCD"\ndp[0] = 1 (\'a\')\ndp[1] = (dp[0] + 1) (\'AB\' = \'A\' +\'B\') + 1 (\'b\') = 3\ndp[2] = (dp[1] + 2) (\'ABC\' = \'AB\' + \'C\', \'BC\' = \'B\' +\'C\' ) + 1 (\'c\') = 6\ndp[3] = (dp[2] + 3) (\'ABCD\' = \'ABC\' + \'D\', \'BCD\' = \'BC\' +\'D\' , \'CD\' = \'C\' + \'D\' ) + 1 (\'D\') = 10\n\n\n\nNow take repeat characters into consideration\nthe formula become\n**dp[i] = dp[i-1] + (i+ 1 -last[c]) - last2[c]**\nwhere c = s[i], last[c] is the last occurence index of c + 1, last2[c] is the range between latest occuring two c\nconsider the following case s = "ABCC"\n\ndp[0] ~ dp[1] is same as "ABCD" because each of the character is distinct\ndp[2] = (dp[1] + 2) (\'ABC\' = \'AB\' + \'C\', \'BC\' = \'B\' +\'C\' ) + (\'C\') =\n    \'ABC\' + \'BC\' + \'C\' =  3 + 2 + 1 = 6\ndp[3] = (dp[2] + 3) - 3 (\'ABCC \'= \'ABC\' + \'C\', \'BCC\' = \'BC\' +\'C\' , \'CC\' = \'C\' + \'C\' ) + (\'C\')  = \n\t\'ABCC\' + \'BCC\' + \'CC\' + \'C\' = 2 + 1 + 0 +\uFF11 = 4\n  \nLet\'s look at dp[2] and dp[3], first we pretend s[3] is a distinct character\n\nThen dp[3] = dp[2] + 3 + 1 =   ( (3+1) + (2+1) + (1+1) ) + 1 \nBut s[3] = \'C\' which is repeated, \n\nso instead of plus one, the previous substing from dp[2] with \'C\' should minus one  \n(3) + (2) + (1)  become (3-1) + (2-1) + (1-1), this is why we need minus **last2[c]** in the formula, note that **last2[c]** is the range between latest occuring two \'C\', because previous occuring of \'C\' are already considered\nAnd the adding number **(i+ 1 -last[c])** is because only this number of substring from previous dp are not influcenced\n\nNote that the size n dp list can be reduce to 1 because we only need previous dp value\n```\nclass Solution:\n    def uniqueLetterString(self, s: str) -> int:\n        last = collections.defaultdict(int)\n        last2 = collections.defaultdict(int)\n        dp = res = 0\n        for i,c in enumerate(s):\n            dp = dp + (i+ 1 -last[c]) - last2[c]\n            last2[c] = i+1 - last[c]\n            last[c] = i+1\n            res += dp\n        return res\n```
[]