[Python] O(N^3), O(N^2), O(N) solutions
\nclass Solution:\n\n\t# O(N^3) TLE\n    def uniqueLetterString(self, s: str) -> int:\n            \n        cnt = 0\n        for i in range(len(s)):\n         
```\nclass Solution:\n\n\t# O(N^3) TLE\n    def uniqueLetterString(self, s: str) -> int:\n            \n        cnt = 0\n        for i in range(len(s)):\n            c = {}\n            uniq = 0\n            for j in range(i+1, len(s)+1):\n                el = s[j-1]\n                c[el] = c.get(el, 0) + 1\n                if c[el] == 1:\n                    uniq += 1\n                elif c[el] == 2:\n                    uniq -= 1\n                cnt += uniq\n                \n        return cnt % int(1e9 + 7)\n    \n\t# O(N^2) TLE, keep a dict and iterate back and forth the array extending it, so we don\'t have\n\t# to initialise it every time. I thought it was the best possible runtime before seeing the solution\'s intuition\n    def uniqueLetterString(self, s: str) -> int:\n        \n        if len(s) == 0:\n            return 0\n        \n        cnt = w = uniq = 0\n        c = {s[0]: 0}\n        direction = 1\n\n        def move(pos, sign):\n            ic = s[pos]\n            old = c.get(ic, 0)\n            c[ic] = old + sign\n            if c[ic] == 1:\n                return 1\n            elif (c[ic] == 2 or c[ic] == 0) and old == 1:\n                return -1\n            else:\n                return 0\n\n        while w < len(s):\n            if direction:\n                for i in range(w, len(s)):\n                    uniq += move(i, 1)\n                    cnt += uniq\n                    uniq += move(i - w, -1)\n\n                direction = 0\n                uniq += move(len(s) - w - 1, 1)\n                w += 1\n            else:\n                for i in range(len(s) - w - 1, -1, -1):\n                    uniq += move(i, 1)\n                    cnt += uniq\n                    uniq += move(i + w, -1)\n\n                direction = 1\n                uniq += move(w, 1)\n                w += 1\n                \n        return cnt % int(1e9 + 7)\n    \n\t\n\t# O(N) Implemented from the solution, passes\n    def uniqueLetterString(self, S: str) -> int:\n        index = collections.defaultdict(list)\n        for i, el in enumerate(S):\n            index[el].append(i)\n\n        cnt = 0\n        for val in index.values():\n            val = [-1] + val + [len(S)]\n            for i in range(1, len(val)-1):\n                cnt += (val[i] - val[i-1]) * (val[i+1] - val[i])\n        return cnt % int(1e9 + 7)\n```
[]