[Python] Linear in time and constant in space
Main ideas:\n We can count for every character x in s, how many ways to be found as a unique char. To do that, you need to know the last time I saw x and the ne
Main ideas:\n* We can count for every character x in s, how many ways to be found as a unique char. To do that, you need to know the last time I saw x and the next time I will see x again.\n\n* last_seen array holds the information of the last two times a capital letter was seen. last_seen[j] is the the last two times x was seen, where j = ord(x) - ord(\'A\').\n\n* In the one pass loop, I increase the ret by ( last_seen[j][1] - last_seen[j][0] ) * ( i - last_seen[j][1] ), this is the number of ways x to be found as a unique char. And, update the last_seen array.\n\n* Since the one pass loop does not update ret for the last uniuqe characters, we need to go through all letters and increase ret.\n\n```\nclass Solution:\n    def uniqueLetterString(self, s: str) -> int:        \n        last_seen = [ [ -1,-1 ] for _ in range(26) ]\n        ret = 0\n        \n        for i, x in enumerate(s):\n            j = ord(x) - ord(\'A\')\n            ret += ( last_seen[j][1] - last_seen[j][0] ) * ( i - last_seen[j][1] )\n            last_seen[j] = [ last_seen[j][1], i ]\n            \n        for k in range(26):\n            ret += ( last_seen[k][1] - last_seen[k][0] ) * ( len(s) - last_seen[k][1] )\n        \n        return ret\n```
['Python']