Python O(n) easy solution with explanations
\nclass Solution(object):\n    def uniqueLetterString(self, s):\n        """\n        :type s: str\n        :rtype: int\n        """\n        \'\'\'\n        co
```\nclass Solution(object):\n    def uniqueLetterString(self, s):\n        """\n        :type s: str\n        :rtype: int\n        """\n        \'\'\'\n        core idea:\n        Let\'s define:\n            count: the additional unique chars num when we add one letter to a string\n            X: the current letter\n            index: the index of X\n        when we add a letter X, the string has 3 situlation:\n        1. string don\'t include same letter\n        ________X\n        |<- 1 ->|\n        So, compre to the last operation, we will get additional unique chars count for letter X in zone 1, with the letter X add up we get i + 1 cases that contain unique X\n\n        2. string include same letter\n        ________X_______X\n        |<- 1 ->|<- 2 ->|\n        for this situation, we know that the possible cases(substring include X, show in zone 1) from start to the first letter X have been count, with the new X add up we need to minus it first and addup the possbile case between the last two letter X\n\n        3. \n        ________X_______X_______X\n        |<- 1 ->|<- 2 ->|<- 3 ->|\n        the same idea as the last case. When the last X add to string, We need to minus the num we have count between zone 2, and add up count between zone 3\n\n        \n        \'\'\'\n        result = 0\n        # a list to record the last added count and last index of the current letter.\n        pre_pos = [[0, -1] for _ in range(26)]\n        count = 0\n        for i in range(len(s)):\n            char = s[i]\n            pre_count, pre_index = pre_pos[ord(char) - ord(\'A\')]\n            # delete the num that we add last and add the count that we current increase\n            count += -1 * pre_count + i - pre_index\n            result += count\n            pre_pos[ord(char) - ord(\'A\')] = [i - pre_index, i]\n        return result\n```\n\nComment for advise or reputation. Thanks
[]