题目描述

给你数字字符串$s$，请你返回$s$中长度为$5$的回文子序列数目。由于答案可能很大，请你将答案对$10^9 + 7$取余 后返回。

提示：

• 如果一个字符串从前往后和从后往前读相同，那么它是回文字符串 。
• 子序列是一个字符串中删除若干个字符后，不改变字符顺序，剩余字符构成的字符串。

样例1

输入：s = "103301"
输出：2
解释：
总共有6长度为5的子序列："10330"，"10331"，"10301"，"10301"，"13301"，"03301" 。
它们中有两个（都是 "10301"）是回文的。

样例2

输入：s = "9999900000"
输出：2
解释：仅有的两个回文子序列是"99999"和"00000"。

限制

• $1 \leq s.length \leq 10^4$
• $s$只包含数字字符。

算法

动态规划+组合

动态规划

状态定义：$f[i][x][y]$表示$0$~$i$中$xy$出现的次数；$g[i][y][x]$表示$i$~$n-1$中$yx$出现的次数。
状态转移：
1. 如果$s[i]=y$则$f[i][x][y]$由两个部分组成，$(1)$$[0,i)$中$xy$的出现次数；$(2)$$[0,i)$中$x$的出现次数$cnt$，这些$x$可以和$s[i]$构成$cnt$个新的$xy$。因此，我们还需要预处理每种数字的前缀出现频数。
2. 如果$s[i] \neq y$，则只有$(1)$。同理分析后缀$g$，得到状态转移方程如下：
$f[i][x][y] = f[i - 1][x][y] + c[x][i - 1]$ ,$s[i]=y$
$f[i][x][y] = f[i - 1][x][y]$ ,$s[i] \neq y$
$g[i][y][x] = g[i + 1][y][x] + c[x][n - 1] - c[x][i]$ ,$s[i]=y$
$g[i][y][x] = g[i + 1][y][x]$ ,$s[i] \neq y$

组合

遍历每个位置$i$，以这个位置为回文中心，将两边长度为$2$的镜像对称的子序列交叉组合起来就行了，即
$res=\Sigma_{i=2}^{n-3}f[i - 1][x][y] \times g[i + 1][y][x]$

复杂度分析

$f$数组和$g$数组的规模都是$100n$，前缀和数组$c$的规模是$10n$，额外空间复杂度为$O(\Sigma^2n)$，$\Sigma$为字符集大小，本题中$\Sigma=10$；
动态规划需要枚举$xy$，最内层还有$O(n)$的时间复杂度，整体时间复杂度为$O(\Sigma^2n)$；组合的时间复杂度也相同，因此这也是整个算法的时间复杂度。

typedef long long LL;

const int N = 1e5 + 5;
int f[N][10][10], g[N][10][10];

class Solution {
public:
    const int MOD = 1e9 + 7;
    int countPalindromes(string s) {
        int n = s.size();
        if(n < 5) return 0;
        vector<int> c[10];
        for(int x = 0; x <= 9; x++) {
            c[x] = vector<int>(n);
            c[x][0] = s[0] == (char)('0' + x);
            for(int i = 1; i < n; i++) {
                c[x][i] = c[x][i - 1] + (s[i] - '0' == x);
            }
        }
        memset(f, 0, sizeof f);
        memset(g, 0, sizeof g);
        for(int x = 0; x <= 9; x++) {
            for(int y = 0; y <= 9; y++) {
                for(int i = 1; i < n; i++) {
                    int num = s[i] - '0';
                    f[i][x][y] = f[i - 1][x][y] + (num == y? c[x][i - 1]: 0);
                    num = s[n - 1 - i] - '0';
                    g[n - 1 - i][y][x] = g[n - i][y][x] + (num == y? c[x][n - 1] - c[x][n - 1 - i]: 0);
                }
            }
        }
        LL ans = 0;
        for(int x = 0; x <= 9; x++) {
            for(int y = 0; y <= 9; y++) {
                for(int i = 2; i < n - 2; i++) {
                    ans = (ans + (LL)f[i - 1][x][y]*g[i + 1][y][x]) % MOD;
                }
            }
        }
        return ans;
    }
};