LC 5220. 两个回文子字符串长度的最大乘积

https://leetcode-cn.com/problems/maximum-product-of-the-length-of-two-palindromic-substrings/

这题的关键字在于如何计算：以 `a[i]` 字符为结尾，能产生的最长回文串。得到每个位置所能产生的最长回文串长度之后，就可以更新为 “截止到这个位置能产生的最大回文串” 的信息。

这段代码如下，其中我唯一不太确定的地方就是这个时间复杂度，主要就是 `while s[i] != s[p]` 这段。

def maxdist(s):
    dist = [1] * n

    for i in range(1, n):
        d = dist[i - 1]
        p = i - d - 1

        if p < 0:
            # try small dist.
            d -= 2
            p += 2

        while s[i] != s[p]:
            d -= 2
            p += 2

        if s[i] == s[p]:
            dist[i] = d + 2

        # don't need even length.
        # elif s[i] == s[i - 1]:
        #     dist[i] = 2

    for i in range(1, n):
        dist[i] = max(dist[i], dist[i - 1])

    return dist

不过好像这样也没有问题，因为对于当前位置使用更少的长度的话，那么后面位置检查的长度也会更少。运行起来有点像two chasing pointers的感觉，所以时间复杂度还是有保证的。