难度: Hard
给你数字字符串 s ，请你返回 s 中长度为 5 的 回文子序列 数目。由于答案可能很大，请你将答案对 109 + 7 取余 后返回。
提示：
示例 1：
输入：s = "103301" 输出：2 解释： 总共有 6 长度为 5 的子序列："10330" ，"10331" ，"10301" ，"10301" ，"13301" ，"03301" 。 它们中有两个（都是 "10301"）是回文的。
示例 2：
输入：s = "0000000" 输出：21 解释：所有 21 个长度为 5 的子序列都是 "00000" ，都是回文的。
示例 3：
输入：s = "9999900000" 输出：2 解释：仅有的两个回文子序列是 "99999" 和 "00000" 。
提示：
1 <= s.length <= 104s 只包含数字字符。运行时间: 152 ms
内存: 16.7 MB
class Solution:
def countPalindromes(self, s: str) -> int:
s = list(map(int, s))
# a[3] = 当前A状态3的个数
# b[5][3] = 当前子序列AB=35的[个数,索引和]
# d[5][3] = 当前子序列ABCD=35X5的个数
a = [0] * 10
b = [[[0, 0] for j in range(10)] for i in range(10)]
d = [[0 for j in range(10)] for i in range(10)]
ans = 0
M = 10 ** 9 + 7
for i, num in enumerate(s):
# 计算e
for y in range(10):
ans = (ans + d[num][y]) % M
# 计算d
for x in range(10):
d[x][num] += (i-1) * b[x][num][0] - b[x][num][1]
d[x][num] %= M
# 计算b
for x in range(10):
b[x][num][0] += a[x]
b[x][num][1] += a[x] * i
a[num] += 1
return ans
本题解使用动态编程的方法来计算所有长度为5的回文子序列的数量。思路是使用多层哈希结构（数组）来维护字符的各种可能组合及其出现的次数和索引和。主要步骤分为：1) 更新a数组，它维护每个数字字符的出现次数；2) 更新b数组，它维护每种两字符组合的出现次数及索引和；3) 更新d数组，它维护每种四字符组合（形如ABCD）的出现次数；4) 通过对d数组的查询来统计所有可能的回文子序列。由于回文的特性，第五个字符必须与第一个字符相同，因此通过匹配这种模式来累计计数。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def countPalindromes(self, s: str) -> int:
s = list(map(int, s))
a = [0] * 10 # Count of each digit
b = [[[0, 0] for j in range(10)] for i in range(10)] # Count and sum of indexes for pairs
d = [[0 for j in range(10)] for i in range(10)] # Count of quads
ans = 0
M = 10 ** 9 + 7
for i, num in enumerate(s):
# Calculate counts for 5-length palindromes
for y in range(10):
ans = (ans + d[num][y]) % M
# Update quads based on pairs
for x in range(10):
d[x][num] += (i-1) * b[x][num][0] - b[x][num][1]
d[x][num] %= M
# Update pairs based on digit count
for x in range(10):
b[x][num][0] += a[x]
b[x][num][1] += a[x] * i
# Update count of each digit
a[num] += 1
return ans
直接遍历所有长度为5的子序列来检查是否为回文，虽然直观但效率较低，时间复杂度为O(n^5)，其中n是字符串的长度。使用三层数组结构（a、b、d）能够利用动态规划的方法，将问题分解为多个较小的子问题，并存储中间结果，从而避免重复计算，显著提升算法效率。数组a、b、d分别记录了不同长度组合的字符出现情况，使得通过更新和查询这些数组，可以在O(n)的时间复杂度内完成对所有长度为5的回文子序列的计数。
d数组用于记录每种四字符组合的出现次数。在计算过程中，每遇到一个新字符，就尝试将其与之前记录的所有可能的三字符组合（由b数组记录）结合，形成新的四字符组合，同时更新d数组。当处理到字符串的某个位置时，对于当前字符，检查所有以此字符结尾能形成的四字符组合（即查看d数组），检查它们能否与之前的字符配对成为回文子序列。因此，d数组使得我们能够高效地统计所有可能的以当前字符结尾的回文子序列数量。
这个表达式用于计算与当前字符配对的所有可能的三字符组合（由b数组记录）的更新。其中`b[x][num][0]`是到目前为止与当前字符配对的字符x的出现次数，而`b[x][num][1]`是这些字符出现位置的索引和。表达式中的`(i-1) * b[x][num][0] - b[x][num][1]`是计算所有以x和当前字符num为中心的三字符组合能形成的四字符组合的数量。这是通过计算当前位置i之前所有可能的配对位置与当前位置的差的和来实现的，从而确保更新d数组时能正确反映所有四字符组合的出现次数。
在每次处理字符串中的一个新字符时，我们通过查询d数组来统计可能的回文子序列。具体地，对于当前字符，如果它能与某个四字符组合形成回文（即当前字符等于该四字符组合的第一个字符），我们就通过查看d数组中记录的该四字符组合的出现次数来增加回文子序列的计数。这种方法确保了每次遇到一个可能的回文结尾时，能够快速查询并累加之前所有匹配的四字符组合的数量，从而高效地统计出所有长度为5的回文子序列的总数。