Palindromic Substrings

#Manacher O(n) space and time

class Solution:
    def countSubstrings(self, s: str) -> int:
        p = self.preprocessString(s)
        n = len(p)

        l, r, c = -1, -1, -1
        pals = [1]*n

        for i in range(n):
            if i > r:
                l = c = r = bound = i
            else:
                mirr = 2*c - i
                pals[i] = min(pals[mirr], 2*(r - i) + 1)
                bound = mirr - pals[mirr]//2

            if bound != l:
                continue

            l = i - pals[i]//2
            c = i
            while l > 0 and r < n-1 and p[l-1] == p[r+1]:
                pals[i] += 2
                l -= 1
                r += 1

        res = 0
        for x in pals:
            res += (x+1)//4

        return res

    def preprocessString(self, s):
        n = len(s)
        res = ["#"]*(2*n+1)

        for i in range(n):
            res[2*i+1] = s[i]

        return res