Python O(n) with intuition / step-by-step thought process
This is one of my first Hard and I\'m writing in extreme detail to help myself fully understand and internalize this. Even after solving it I have trouble under
This is one of my first Hard and I\'m writing in extreme detail to help myself fully understand and internalize this. Even after solving it I have trouble understanding most other solution posts.\n\nIt\'s easiest to understand what this problem actually means with a brute force solution:\n```\nclass Solution:\n    def uniqueLetterString(self, s: str) -> int:\n        r=0\n        for i in range(len(s)):\n            for j in range(i, len(s)):\n                ss=s[i:j+1]\n                unique=sum([ 1 for (i,v) in Counter(ss).items() if v == 1 ])\n                r+=unique\n        return r\n```\n(The two loops are generating start and end indices for all possible substrings)\n\nFor every possible substring (for abc meaning a,b,c,ab,bc,abc), we sum the number of characters that appear exactly once in the substring, and return a global sum of sums.\n\nThe problem says s can be up to 10^5 length, and this code is O(n^3), so you can tell we have to do better right away (you can\'t even have a double-for-loop with 10^5 iterations each that does nothing, much less string processing).\n\nOne intuition is, if we can\'t process each substring (which is inherently O(n^3)) maybe we can process each individual character. The key is that for any particular substring, characters don\'t affect each other (like, \'a\' doesn\'t care about how many \'b\' there are). You can kind of see this by reading this horrible solution, which is O(n^3) but even worse:\n```\nclass Solution:\n    def uniqueLetterString(self, s: str) -> int:\n        def does_char_appear_once(sub, t):\n            num=0\n            for c in sub:\n                if c==t:\n                    num+=1\n            return num==1\n            \n        r=0\n        for c in string.ascii_uppercase:\n            for i in range(len(s)):\n                for j in range(i, len(s)):\n                    if does_char_appear_once(s[i:j+1], c):\n                        r+=1\n        return r\n```\nThe intuition is that while it\'s still processing every substring, the outermost loop means it\'s only looking at one character at a time when it looks at substrings. Understanding that, the next step is, how can we stop processing every substring? Let\'s look at the first example testcase:\n```\nInput: s = "ABC"\nOutput: 10\nExplanation: All possible substrings are: "A","B","C","AB","BC" and "ABC".\nEvery substring is composed with only unique letters.\nSum of lengths of all substring is 1 + 1 + 1 + 2 + 2 + 3 = 10\n```\nThe big logic jump is, "how much does each character contribute to the overall sum"?\nFrom the earlier perspective,\n* "A" contributes 3 because it occurs in three substrings (A,AB,ABC)\n* "B" contributes 4 because it occurs in four substrings (B,AB,BC,ABC)\n* "C" contributes 3 because it occurs in three substrings (C,BC,ABC)\n\nIt\'s pretty simple to see that for \'A\' it contributes 3 because the string is length 3, and all substrings that contain it start at 0.\n\'C\' is the opposite case: it contributes 3 because the string is length 3 and all substrings that contain it end at it.\n\nBut suppose the string is actually \'ABCABC\'. The first \'A\' still only contributes 3 because the next \'A\' is the edge, rather than the end of the string.\nSo far, you can kind of get an idea, let\'s keep track of the index of each character occurrence and add the span between them. \n```\nclass Solution:\n    def uniqueLetterString(self, s):\n        indices=defaultdict(list)\n        for i in range(len(s)):\n            indices[s[i]].append(i)\n        \n        r=0\n        for k,v in indices.items():\n            for i in range(len(v)):\n                if i==0:\n                    prev=-1\n                else:\n                    prev=v[i-1]\n                \n                if i==len(v)-1:\n                    nxt=len(s)\n                else:\n                    nxt=v[i+1]\n                    \n                r+=nxt-prev-1\n        return r\n```\nThis works by\n1. Generate a dict mapping each character (A,B,C,...) to the list of indices it occurs.\n2. For each character, add up the span between consecutive occurrences of the same character. It\'s a little trickier because the start and end of string can also act as the boundary, so that\'s the len(s) and -1 defaults. It\'s clear they are the necessary values by considering how A and C can both be satisfied in the "ABC" example.\n\nBut actually, this isn\'t quite right. This works as expected for the first and last character, but for \'B\', it also thinks there are only 3 substrings when there are 4. Why are there 4? A longer example makes this easier to understand:\n\'ABCDEFG\'\nThe contribution of \'A\' and \'G\' make sense and are still correct. But for middle ones such as \'C\' it\'s wrong. Think about the effect of adding another character to the string:\n\'ABCDEFGH\' (added H)\n\'A\' gets one more substring, but to see the problem for \'C\', consider that for each possible ending character to the right of \'C\' (DEFGH), a substring could start at any of \'A\', \'B\', \'C\'. For example, by adding \'H\' we added not just 1 substring, but a substring for each left character:\n\'ABCDEFGH\'\n\'BCDEFGH\'\n\'CDEFGH\'\n\nThis shows there is a multiplicative relationship between left span and right span. Incrementing right_span by 1 adds left_span to the total! Once you understand that, the solution is self-evident: add left_span * right_span, where left_span is the distance to the left to the previous occurence of the character or start of string, and right_span is the same for right side.\nFinal code:\n```\nclass Solution:\n    def uniqueLetterString(self, s):\n        indices=defaultdict(list)\n        for i in range(len(s)):\n            indices[s[i]].append(i)\n        \n        r=0\n        for k,v in indices.items():\n            for i in range(len(v)):\n                curr=v[i]\n                if i==0:\n                    prev=-1\n                else:\n                    prev=v[i-1]\n                \n                if i==len(v)-1:\n                    nxt=len(s)\n                else:\n                    nxt=v[i+1]\n                    \n                r+=(curr-prev)*(nxt-curr)\n        return r\n```\n\t\t\n\nI think it can be optimized pretty easily to not need O(n) space storing the indices but haven\'t gotten around to trying that.
['Python3']