Simple Multiplication/Modulo O(26n)
posting here because its slightly different from others posts so far.\n\n# Intuition\nThe number of complete substrings ending at index \'i\' is going to be max
posting here because its slightly different from others posts so far.\n\n# Intuition\nThe number of complete substrings ending at index \'i\' is going to be max of 26. This is because if a letter is repeating exactly \'k\' times, then there are only 26 such possibilities at \'i\' (namely, k, 2k, 3k, ...)for each alphabet.\n\n# Approach\nWe will use the commutative property of integers. \n\nWe would assign 26 primes to 26 alphabets. if there is \'k\' repeating alphabet from index i .. j, then it reasons to say that p\\*\\*k + h[i] == h[j] if there is such substring. Similarly, If there are two characters, then p1\\*\\*k * p2\\*\\*k + h[i] == h[j]. So on and so forth. We would use Modulo to keep it within limit.\n\nThe \'cs\' array is to keep track of recent 26 alphabets. It helps us to get prime corresponding to that alphabet and raise to power \'k\'.\n\nWhen we have a index location which has alphabet diff > 2 , then badi helps to reset our quest to find \'k\' repeating substring.\n\n# Complexity\n- Time complexity:\n    O(26n)\n- Space complexity:\n    O(1)\n\n# Code\n```\nclass Solution:\n    def countCompleteSubstrings(self, word, k):\n        pl = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101]\n        hv, cs, res, M, ch, badi  = [0]*len(word), [], 0, 10**9+7, 1, -1\n        pk, pj = [(j**k) % M for j in pl], ord(word[0])\n        for i, w in enumerate(word):\n            j = ord(w) - 97\n            if i and abs(j-pj) > 2: badi = i-1\n            if j in cs: cs.remove(j)\n            cs.append(j)\n            ch, pj = (ch*pl[j]) % M, j\n            hv[i], ii, tch = ch, i, 1\n            if i < k-1: continue\n            for j in cs[::-1]:\n                ii -= k\n                if ii < -1 or ii < badi: break \n                tch = (tch *pk[j]) % M\n                base = 1 if ii == -1 else hv[ii]\n                if ((base*tch) % M)  == hv[i]: res += 1\n        return res   \n```
['Python3']