回文串是指一个字符串，其正读和反读都一样。若一个回文串的长度为 $n$，那么我们只需要知道前 $\left\lceil \frac{n}{2} \right\rceil$ 个位置，就可以知道整个回文串。在这里我们把这前 $\left\lceil \frac{n}{2} \right\rceil$ 个位置称为 关键位。

我们要找出 字典序小于等于 $s$ 的回文串 数量，我们可以分成两个部分。

1. “前缀更小”的回文串数量，也就是 字典序小于$s$ 的回文串数量。

   可以通过遍历关键位 $i$，统计第 $i$ 位选择比 $s_i$ 更小字母的对应回文串数量。设 $t$ 为第 $i$ 位选择 $s_i$ 更小字母的可选择数量。

   答案贡献 1：回文串长度是 奇数，也就是说第 $i$ 位为中心。贡献为 $t$。

   答案贡献 2：回文串长度是 偶数。那么我们目前可以确定的是 $2i$ 个位置，剩下的位置数量是 $n - 2i$ 个位置，这些位置可以选择填入任意字符。贡献为 $t \times 剩余长度的回文总数$。

2. “前缀相同”的回文串数量。可以使用 Manacher算法(马拉车算法) 来解决，时间复杂度 $O(n)$。