O(N) Python Approach using Defaultdict
\n\nclass Solution:\n    def uniqueLetterString(self, s: str) -> int:\n        mydict = defaultdict(list)\n        for char in [chr(65 + i) for i in range(26)]:
```\n\nclass Solution:\n    def uniqueLetterString(self, s: str) -> int:\n        mydict = defaultdict(list)\n        for char in [chr(65 + i) for i in range(26)]:\n            mydict[char].append(-1)\n        for i, char in enumerate(s):\n            mydict[char].append(i)\n        for char in [chr(65 + i) for i in range(26)]:\n            mydict[char].append(len(s))\n            mydict[char] = mydict[char][::-1]\n        \n        summ = 0\n        for char in s:\n            cur = mydict[char][-2]\n            pre = mydict[char][-1]\n            nxt = mydict[char][-3]\n            left = cur - pre\n            right = nxt - cur\n            summ += left*right\n            mydict[char].pop()\n            \n        return summ\n```\n\nFor "ABAB", mydict will be like:\n"A": [4, 2, 0, -1]\n"B": [4, 3, 1, -1]\nmydict records the index where a letter appears. The list is reversed because removing an element at the end using pop() is fast, but removing an element at the beginning of a list is slow.\n\nI met a similar problem during Amazon online assesment. I can only come up with the O(N^2) method, which failed some large test cases. The problem is this one: https://leetcode.com/discuss/interview-question/1526418/Count-strength-of-password-or-amazon/1120513
['String', 'Python']