O(n) easy python solutions!
first scan the string and create a dictionary that holds the list of indexes for each char\n\ne.g. AAABC   -> memo ={\'A\':[0, 1, 2], \'B\': [3], \'C\':[4]}\n\n
first scan the string and create a dictionary that holds the list of indexes for each char\n\ne.g. AAABC   -> memo ={\'A\':[0, 1, 2], \'B\': [3], \'C\':[4]}\n\nnext scan the memo object values for each char, each char can be counted as unique char in all the substrings calculated by the number of countagious/different chars on the left * number of contagous/different chars on the rights\n\n\'\'\'\n\n        memo = defaultdict(list)\n        for i, l in enumerate(s): # O(n) O(n)\n            memo[l].append(i)\n        \n        result = 0\n\n        for k, v in memo.items(): # O(n) O(n)\n            for i, index in enumerate(v):\n                if i - 1 >= 0:\n                    left = index - v[i-1]\n                else:\n                    left = index - (-1)\n                \n                if i + 1 < len(v):\n                    right = v[i+1] - index\n                else:\n                    right = len(s) - index \n\n                result += left*right     \n        return result\n\'\'\'
[]