题目描述
给定一个字符串,长度在 $[3,10^6]$ 之间,至多删除两个字符能得到多少个不同的字符串?
样例
样例输入 #1
ababcc
样例输出 #1
15
样例解释
删除0个字符 ababcc
删除1个字符 babcc
, aabcc
, abbcc
, abacc
, ababc
删除2个字符 abcc
, bbcc
, bacc
, babc
, aacc
, aabc
, abbc
, abac
, abab
思路
计数DP+去重考虑。如果对这个不了解的话,可以先去做一下 $n$ 长度的字符串当中长度为 $k$ 的不同子序列有多少,这个就是一个景点的dp+去重。
那么我们这里也是同样的思路,假设 $dp[i][j]$ 是前 $i$ 个字符中,删除 $j$ 个字符可以得到的不同串个数($0\le i \le n, 0\le j \le 2$)。初始有 $dp[i][0] = 1$(对于 $i=0$ 也是成立的)。那么对于每一个 $dp[i][j]$ ,在不去重的情况下,无非就是删除第 $i$ 个字符会对答案带来贡献,有 $dp[i][j]=dp[i-1][j-1]+dp[i-1][j]$ 。
接下来我们考虑如何去重。这里去重跟前面那个问题比较像但是又有点区别。比如说字符串 abcdec
,如果删除3到5的 cde
或者删除4到6的 dec
,那么都会得到 abc
,但是这两个 c
相隔三个字符,只删除两个再怎么删也出不了重复的情况;反之只要相邻两个以内,比如 abdcec
,删除 ce
或者 ec
都能得到 abdc
,而且重复的方案都和最后那个 c
无关,只会是从 abd
带来的贡献。所以我们就看当前字符最晚一次出现在哪里,如果两者间隔不大于 $2$ (设为 $k$),那么 $dp[i][j]$ 就会有一个 $dp[i-k-1][j-k]$ 的重复方案需要去掉。
代码
#include <stdio.h>
#include <string.h>
typedef long long i64;
const int N = 1000010;
int n, k;
char s[N];
i64 dp[N][3];
int pre[26];
int main()
{
scanf("%s", s + 1), n = strlen(s + 1), k = 2;
dp[0][0] = 1;
for (int i = 1; i <= n; ++i)
{
dp[i][0] = 1;
for (int j = 1; j <= i && j <= k; ++j)
{
dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];
int pre_gap = i - pre[s[i] - 'a'];
if (pre_gap <= j)
dp[i][j] -= dp[pre[s[i] - 'a'] - 1][j - pre_gap];
}
pre[s[i] - 'a'] = i;
}
i64 ans = 0;
for (int j = 0; j <= k; ++j)
ans += dp[n][j];
printf("%lld", ans);
}