题目描述
给你数字字符串$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;
}
};