python O(N) solution with explanation
Before solving this quesion, you need to understand what rule of product and don\'t get confused of subarray, subset, and substring.\n\n#### What is rule of pro
Before solving this quesion, you need to understand what rule of product and don\'t get confused of subarray, subset, and substring.\n\n#### What is rule of product?\nIt is one of counting principles. \nFor example, if we are going to city C from city A, and we need to stop by city B. \nA -> B -> C\nI assume there are three ways that you can go to B from A maybe by taking a bus, taking uber, or riding a bike.\nThen assume you have two ways that you can go to C from B maybe by taking a flight or self-drive.\nSo you will have a total of six ways from A to C.\nA -> B (bus) -> C (flight)\nA -> B (uber) -> C (drive)\nA -> B (bike) -> C (flight)\nA -> B (bus) -> C (drive)\nA -> B (uber) -> C (flight)\nA -> B (bike) -> C (drive)\n\n\nIf you need further explanation of what rule of product, you can click the link below:\n[https://en.wikipedia.org/wiki/Rule_of_product](http://)\n\n#### What difference between subarray, subset, and substring?\nBasically, subarray(substring) has order and continuity, but subset doesn\'t.\nFor example:\nnums = [1, 2, 3]\nThe subarray of nums is: [1], [1,2], [1,2,3], [2], [2,3], [3].\nThe subset of nums is: [1], [1,2], [1,2,3], [2], [2,3], [3], **[1,3]**. <- The order doesn\'t matter in subset, so you can write [1,3] or [3,1]. Both of them are the same subset of nums. \n\nWhen you are writing the subarray, you can think the bracket parenthesis is moving.\n[1] 2] 3] <- There is one place to put left bracket, and there are three place to put right bracket.\nSo we get [1], [1,2], [1,2,3]. 1*3 = 3\n1 [2] 3]  <- There is one place to put left bracket, and there are two place to put right bracket.\nSo we get [2], [2,3]. 1*2 = 2\n1 2 [3]   <- There is one place to put left bracket, and there are one place to put right bracket.\nSo we get [3]. 1*1 = 1\n\nFinally, total subarray of nums is 3+2+1 = 6. \n(formula to reach the total numbe of subarray is n*(n+1)/2)\n\n========================================================\n#### Now back to the question.\n\nWe want to get the sum of unique characters over all substring. \n\nstring = "LEETCODE"\nFor L, there is one place for left bracket, and there are 8 place for right bracket. So 1*8 = 8\n* L:  [ **L** ] E ] E ] T ] C ] O ] D ] E ]  => 1*8 = 8\n* For first E, there is two places for left bracket, and there is 1 place for right bracket. So 2*1 = 2\n* E:  [ L [ **E** ] E T C O D E => 21 = 2; \n*  L E [ **E** ] T ] C ] O ] D ] E => 1*5 = 5; \n* L E E [ T [ C [ O [ D [ **E** ] => 5*1 = 5\n* T: [ L [ E [ E [ **T** ] C ] O ] D ] E ] => 4*5 = 20\n* C: [ L [ E [ E [ T [ **C** ] O ] D ] E ] => 5*4 = 20\n* O: [ L [ E [ E [ T [ C [ **O** ] D ] E ] => 6*3 = 18\n* D: [ L [ E [ E [ T [ C [ O [ **D** ] E ] => 7*2 = 14\n\nFinally, the answer is 8+2+5+5+20+20+18+14 = 92.\n\nIn my solution:\n\nFirst step: I will store all characters index into python dictionary and all unique character into set.\ndict_index:  {\'L\': [0], \'E\': [1, 2, 7], \'T\': [3], \'C\': [4], \'O\': [5], \'D\': [6]}\nseen:  {\'D\', \'L\', \'T\', \'C\', \'O\', \'E\'}\n\nSecond step: Use seen set to traversal all dictionary, then use the rule of product ideal to get score for each character.\n\nFinal step: Sum up all scores.\n\n```\nclass Solution:\n    def uniqueLetterString(self, s: str) -> int:\n        dict_index = {}\n        seen = set()\n        \n        for i in range(len(s)):\n            if s[i] not in seen:\n                seen.add(s[i])\n                dict_index[s[i]] = [i]\n            else:\n                dict_index[s[i]].append(i)\n        \n        print("dict_index: ", dict_index)\n        print("seen: ", seen)\n\n        n = len(s)\n        total = 0\n        \n        for i in seen:\n            if len(dict_index[i]) == 1:\n                left_bracket = -1\n                right_bracket = n\n                # Rule of product\n                total += (dict_index[i][0] - left_bracket)*(right_bracket - dict_index[i][0])\n            else:\n                right_bracket = n\n                while dict_index[i]:\n                    cur = dict_index[i].pop()\n                    left_bracket = dict_index[i][-1] if dict_index[i] else -1\n                    # Rule of product\n                    total += (cur - left_bracket)*(right_bracket - cur)\n                    right_bracket = cur\n            \n        return total\n\n# Input: s = "ABC"\n# Output: 10\n# Explanation: All possible substrings are: "A","B","C","AB","BC" and "ABC".\n# Every substring is composed with only unique letters.\n# Sum of lengths of all substring is 1 + 1 + 1 + 2 + 2 + 3 = 10\n\nif __name__ == \'__main__\':\n\n    # Example 1\n    s = "ABC"\n    solution = Solution()\n    print(f"s = {s}")\n    print(f"uniqueLetterString = {solution.uniqueLetterString(s)}")\n\n    # Example 2\n    s = "ABA"\n    solution = Solution()\n    print(f"s = {s}")\n    print(f"uniqueLetterString = {solution.uniqueLetterString(s)}")\n\n    # Example 3\n    s = "LEETCODE"\n    solution = Solution()\n    print(f"s = {s}")\n    print(f"uniqueLetterString = {solution.uniqueLetterString(s)}")\n```\n\n\n\n
['Python']