Prefix Sum and Building Substrings in a Smart Way || Detailed Explanation || Video Included
Video\nhttps://youtu.be/J58CDFAkNxo\n# Intuition\n Describe your first thoughts on how to solve this problem. \nValid substrings have to have length % k == 0.\n
# Video\nhttps://youtu.be/J58CDFAkNxo\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nValid substrings have to have length % k == 0.\n# Approach\n<!-- Describe your approach to solving the problem. -->\nLets think of how to validate both of our criteria for the substring.\n1. Lets do the second one first since its easy.  The difference between any two adjacent characters has to be at most 2.  So just check as we go for the next character and if its more than 2 diff from the last one we had we just make a new string with characters starting at the new character.  Otherwise add on to the old string.  Can use ASCII value to check for difference. \n2. For each character to occur k times we can maintain a prefix sum for every index then as we build up our string use each index as the possible end index for the substring.  The biggest substring we can build is 26*k length where every character a-z occurs k times so lets just traverse back from our current index to index curr - k then curr - 2k then curr - 3k... to curr-26k or until we are out of bounds whatever happens first.  We can check for each of these possible substrings in O(1) to see if its valid using the prefix sum.  We compare the count of every char at the right index to the left index and the difference has to be either k or 0.  If its 0 the char is not in the substring, and if its k then the char is in there k times.  Anything else produces an invalid string.\n\nI used a hash map to store prefix sums with the key being the index and the value being a hash map of letter counts for that index but an array works also. For each new letter, copy the dictionary of counts for the previous letter and just add the current letter we are on.  Every time you hit a new chunk where condition 1 fails reset your hash map and update the left bound of the chunk to be the curr index.  This didn\'t have any TLE errors in Python that people were talking about. \n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(n) because 26 is constant if you want to include 26 its O(26^2 * n)\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(n) or O(26*n)\n\n# Code\n```\nclass Solution:\n    def countCompleteSubstrings(self, word: str, k: int) -> int:\n        prefixes = {}\n        prefixes[-1] = Counter()\n        l = 0\n        res = 0\n        for r in range(len(word)):\n            if abs(ord(word[r]) - ord(word[r - 1] if r > 0 else word[r])) > 2:\n                prefixes = {}\n                prefixes[r-1] = Counter()\n                l = r\n            prefixes[r] = prefixes[r-1].copy()\n            prefixes[r][word[r]] += 1\n            for i in range(1, 27):\n                left = r - k * i\n                if left < l - 1:\n                    break\n                check = True\n                left_prefixes = prefixes[left]\n                right_prefixes = prefixes[r]\n                for key in right_prefixes:\n                    diff = right_prefixes[key] - left_prefixes[key]\n                    if diff != 0 and diff != k:\n                        check = False\n                        break\n                res += check\n        return res\n```
['Python3']