Python: O(26*N)
We count how many substring contain specific character without recurring.\n\nWe take  BABCAB as example, we count how many substring contain B (idx=2). There ar
We count how many substring contain specific character without recurring.\n\nWe take  `BABCAB` as example, we count how many substring contain `B (idx=2)`. There are `AB`, `B`, `BC`, `BCA`, `ABC` and `ABCA`.\n\nFirst, we ignore other characters: `BxBxxB`. Then, there is *1* `x` in the left of `B (idx=2)` before touching the first `B(idx=0)` and there are *2* `x` in the right of `B (idx=2)` before touching the second `B (idx=5)`. How many substring contain `B (idx=2)` without touching other `B`? The answer is: `(1+1) * (2+1) = 6`.\n\nTherefore, we are able to get answer count by checking every character via this method.\n\n```\nclass Solution:\n    def uniqueLetterString(self, s: str) -> int:\n        ans = 0\n        idx_recorder = collections.defaultdict(list)\n        n = len(s)\n        \n        # record the index for every character\n        # s = "ABCA"\n        # {\n        #     "A": [0, 3],\n        #     "B": [1],\n        #     "C": [2],\n        # }\n        for idx in range(len(s)):\n            c = s[idx]\n            idx_recorder[c].append(idx)\n        \n        \n        def helper(idxes):\n            ans = 0\n\n            for i in range(len(idxes)):\n                # Count the number of substring which contain the character without duplicating\n                # get the left, right value to compute the result.\n                # \n                # Take the middle A (idx=3) as example\n                # s = \'AxxAxxxAxx\'\n                #         -\n                # left = 3 - 0 = 3 \n                # right = 7 - 3 = 4\n                #\n                # The number of substring which contain this A (idx=3) without containing\n                # other A is 3 * 4 = 12\n                \n                if i == 0:\n                    # If it is a first one: it means that there is\n                    # no duplicate character in left\n                    left = idxes[i] + 1\n                else:\n                    left = idxes[i] - idxes[i-1]\n                \n                if i == len(idxes) - 1:\n                    # If it is a last one: it means that there is\n                    # no duplicate character in right side\n                    right = n - idxes[i]\n                else:\n                    right = idxes[i+1] - idxes[i]\n                \n                ans += left * right\n                \n            return ans\n        \n        ans = 0\n        for c in idx_recorder:\n            ans += helper(idx_recorder[c])\n        return ans\n```
['Python']