Python Simple O(N) time, O(1) space (No sliding window) with intuition
TL;DR\nMy final solution is at the bottom. I feel like there is a lot of value in seeing the process in coming to a solution rather than just the final answer. 
# TL;DR\nMy final solution is at the bottom. I feel like there is a lot of value in seeing the process in coming to a solution rather than just the final answer. So, I\'ve included my 3 real submissions.\n\n## Basic Solution O(n^2) time, O(1) space\n\nSo, the first way I began thinking about this problem was to start with the most brute force method possible. You try every possible start and end, and if a, b, and c are within that substring then we count it. \n\nIn addition, imagine this scenario. We start at index=0, and we\'ve visited this so far "**aaabc**acacacacb". Since we\'ve already encountered a working substring, we know that any substring with start=0 and end\u22654 end will work. When we encounter this, we just add **len(s) - end** to our total. This leads us to our first basic solution:\n\nBasic solution: O(n^2) time, O(1) space\n```\n    def numberOfSubstrings(self, s: str) -> int:\n        tot = 0\n        \n        # Step 1: do it n^2\n        for start in range(len(s) - 2):\n            a,b,c = False,False,False\n            for i in range(start, len(s)):\n                if s[i] == \'a\':\n                    a = True\n                elif s[i] == \'b\':\n                    b = True\n                elif s[i] == \'c\':\n                    c = True\n                if a and b and c:\n                    tot += len(s) - i\n                    break\n        return tot\n```\nThis is TLE. We can even optimize slightly by exiting early when there are NO substrings found with a given start. After that point, we know we can\'t proceed and our current total is our final total.\n\n## Better solution: O(n) time, O(n) space\n\nNow, in order to truly optimize our solution down from O(n^2), we have to understand where the inefficiencies come from. Consider this: `"aaaaaaaaabcaaa"`. We figured out on the **first(!)** iteration that the first possible substring ends at index=10. However, we keep looping through the string and checking every time! What if, given any index, we can immediately tell where the next A,B, and C are? \n\nIf we did that, then for a given start index, the # of substrings = `len(s) - max(nextA, nextB, nextC)`. \nSo, this is what I did. At every index, I stored the next A,B, and C. Then, in another loop we can immediately tell the number of substrings with our starting index using our formula above. \n```\n\ttot = 0\n\tcAfter = [len(s) for i in range(len(s) + 1)]\n\taAfter = [len(s) for i in range(len(s) + 1)]\n\tbAfter = [len(s) for i in range(len(s) + 1)]\n\tfor i in range(len(s) - 1, -1, -1):\n\t\taAfter[i] = aAfter[i+1]\n\t\tbAfter[i] = bAfter[i+1]\n\t\tcAfter[i] = cAfter[i+1]\n\t\tif s[i] == \'c\':\n\t\t\tcAfter[i] = i\n\t\telif s[i] == \'b\':\n\t\t\tbAfter[i] = i\n\t\telif s[i] == \'a\':\n\t\t\taAfter[i] = i\n\tfor i in range(len(s) - 2):\n\t\tlatest = max(bAfter[i],cAfter[i],aAfter[i])\n\t\tif latest == len(s):\n\t\t\treturn tot\n\t\ttot += len(s) - latest\n\n\treturn tot\n```\n\nThere\'s one main issue with this. We store a list with the next value at each index. However, when we create our list, we only care what the previous value was. That\'s an indication we can just store it in a variable. So, that\'s what we do. \n\nIn our first loop, we just check for the number of substrings starting at every point instead of doing it in a second loop. One downside is we can\'t exit early as we could in the first, but the (much greater) upside is it only takes one pass. \n\n## Final solution: O(n) time, O(1) space\n\n```\n    def numberOfSubstrings(self, s: str) -> int:\n        tot = 0\n        cAfter = bAfter = aAfter = len(s)\n        for i in range(len(s) - 1, -1, -1):\n            if s[i] == \'c\':\n                cAfter = i\n            elif s[i] == \'b\':\n                bAfter = i\n            elif s[i] == \'a\':\n                aAfter = i\n            latest = max(aAfter, bAfter, cAfter)\n            tot += len(s) - latest\n        return tot\n```\n\nThanks for reading! This was my first solution writeup. If you have any comments/feedback, please let me know!\n
[]