Very Easy to understand Dict Solution O(n)
class Solution:\n    def uniqueLetterString(self, s: str) -> int:\n        """\n        Brute force solution is O(n ** 3)\n\t\t\n        To count the total numb
class Solution:\n    def uniqueLetterString(self, s: str) -> int:\n        """\n        Brute force solution is O(n ** 3)\n\t\t\n        To count the total number of unique chars of all substrings is equalling counting: \n        given one letter, how many substrings contains only one such letter\n        String "ABA":\n        first letter "A", on the left it has [""] substring, on the right it has ["A", "AB"] 2 substring, total it has 1 x 2 = 2 combinations\n        second letter "A", on the left it has ["", "B"] 2 substring, on the right it has ["A"] 1 substring, total it has 1 x 2 = 2 combinations\n        letter "B", on the left it has ["", "A"] 2 substring, on the right it has ["B", "BA"] 2 substring, total it has 2 x 2 = 4 combinations\n        so for string "ABA", it has total 8 combinations\n        \n        String "ABC":\n        first letter "A", on the left it has [""] substring, on the right it has ["A", "AB", "ABC"] 3 substring, total it has 1 x 3 = 3 combinations\n        second letter "B", on the left it has ["", "B"] 2 substring, on the right it has ["B", "BC"] 2 substring, total it has 2 * 2 = 4 combinations\n        letter "C", on the left it has ["", "B", "AB"] 3 substring, on the right it has ["C"] 1 substring, total it has 3 x 1 = 3 combinations\n        so for string "ABC", it has total of 10 combinations\n        \n        Time Complexity O(n)\n        """\n        hashMap = {}   # {char: [positions]}\n        for i in range(len(s)):\n            char = s[i]\n            if char in hashMap:\n                hashMap[char].append(i)\n            else:\n                hashMap[char] = [-1]\n                hashMap[char].append(i)\n                \n        count = 0\n        for key in hashMap:\n            positions = hashMap[key]\n            \n            positions.append(len(s))\n            for i in range(1, len(positions) - 1):\n                count = count + (positions[i] - positions[i-1]) * (positions[i+1] - positions[i])\n        return count
['Python']