难度: Medium
给定一个字符串 s ，请计算这个字符串中有多少个回文子字符串。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
示例 1：
输入：s = "abc" 输出：3 解释：三个回文子串: "a", "b", "c"
示例 2：
输入：s = "aaa" 输出：6 解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"
提示：
1 <= s.length <= 1000s 由小写英文字母组成注意：本题与主站 70 题相同：https://leetcode-cn.com/problems/palindromic-substrings/
运行时间: 32 ms
内存: 16.1 MB
class Solution:
def countSubstrings(self, s: str) -> int:
n = len(s)
t = "$#"
for ch in s:
t += ch
t += "#"
n = len(t)
t += "!"
print(t)
f = [0] * n
iMax = rMax = ans = 0
for i in range(1, n):
if i > rMax:
f[i] = 1
else:
f[i] = min(rMax - i + 1, f[2 * iMax - i])
while t[i + f[i]] == t[i - f[i]]:
f[i] += 1
if i + f[i] - 1 > rMax:
iMax = i
rMax = i + f[i] - 1
ans += f[i] // 2
return int(ans)
此题解采用了Manacher算法，用于快速计算字符串中的回文子串数量。思路首先是转换原始字符串s，通过在每个字符间插入特殊字符#（以及首尾添加额外字符），使得处理过程中可以统一奇数长度和偶数长度的回文子串。例如，'abc'变为'$#a#b#c#！'。这种转换让每个字符都成为了潜在的回文中心。接着，使用数组f来存储以每个字符为中心的最长回文半径。通过动态更新中心iMax和当前最远回文右边界rMax来减少不必要的比较，优化算法效率。最终，通过对数组f的遍历，并依据每个位置的回文半径计算回文子串的数量，得到总的回文子串数。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def countSubstrings(self, s: str) -> int:
n = len(s)
t = '$#'
for ch in s:
t += ch
t += '#'
n = len(t)
t += '!'
f = [0] * n
iMax = rMax = ans = 0
for i in range(1, n):
if i > rMax:
f[i] = 1
else:
f[i] = min(rMax - i + 1, f[2 * iMax - i])
while t[i + f[i]] == t[i - f[i]]:
f[i] += 1
if i + f[i] - 1 > rMax:
iMax = i
rMax = i + f[i] - 1
ans += f[i] // 2
return int(ans)
在处理回文子串时，在字符串s中每个字符之间插入特殊字符#，以及在字符串的开头和结尾添加额外的字符（如'$'和'！'），主要是为了将奇数长度和偶数长度的回文子串统一处理。原始字符串中的回文子串可能是奇数长度也可能是偶数长度，通过插入#，每个原始字符周围都有分隔符，这样每个字符都可以作为回文的中心进行考虑，无需分别编写处理奇数和偶数长度回文的逻辑。例如，字符串'abc'通过这种转换后变为'$#a#b#c#！'，无论原始回文串长度是奇数还是偶数，转换后都以#为边界，方便统一处理。
在Manacher算法中，数组f的每个元素f[i]表示以字符t[i]为中心的最长回文子串的半径（包括t[i]本身）。这意味着从字符t[i-f[i]+1]到t[i+f[i]-1]的子串是回文的。由于数组t中每两个原始字符之间都插入了一个#，实际的回文子串长度就是f[i] - 1（去掉中心的t[i]）。因此，以t[i]为中心的回文子串数量可以通过f[i] // 2来计算，这是因为每增加2个单位的回文半径，原字符串s中就多一个回文子串。
在Manacher算法中，iMax是当前已知的回文子串中心的最远右端的最大值，rMax是这些回文子串中心的最远回文右边界。这两个变量的作用是帮助减少算法中不必要的比较，从而提高效率。当我们在位置i尝试扩展回文时，如果i在rMax内，则可以利用对称性，即f[2*iMax - i]（i关于iMax的对称点的f值），来预测f[i]的初始值，减少比较的次数。如果i超出了rMax，那么没有可利用的对称性，需要从1开始扩展。每次当i的回文右边界超过rMax时，就更新iMax为当前的i，同时更新rMax为i + f[i] - 1，保持记录当前已知的最远回文右边界。