题目描述

给定一个字符串，要求删除非空子串后，使得剩下的字符串至少有k种不同字母。输出多少种不同的删除方案对1e9+7取模

思路

为了高效地计算满足条件的删除方案数，我们可以采用滑动窗口（双指针）技术。以下是详细的解决思路：

1.总频率：

首先统计整个字符串中每个字母的出现次数，并计算总不同字母数 D。 如果 D < k，则没有任何删除方案满足条件，直接输出 0。

题目内容

小塔拿到了一个仅包含小写字母的字符串，小塔希望删除其中一个非空连续子串，使得剩下的字符串至少有$k$种不同字母。

小塔想知道，有多少种不同的删除方案?我们定义，若删除的子串位置不同，则视为两种不同的方案。

输入描述

第一行输入两个正整数$n$和$k$，代表字符串的长度以及最终字符串的字母种类最小值。

一个长度为$n$的只包含小写字母的字符串$s$。(保证至少$k$种字符)

$1≤n≤200000$

$1≤k≤26$

输出描述

一个整数，代表删除子串的方案数。

样例1

输入

5 2
aabba

输出

9

说明

删除区间[$1,1$]代表的子串，得到字符串$abba$。

删除区间[$1,2$]代表的子串，得到字符串$bba$。

删除区间[$1,3$]代表的子串，得到字符串$ba$。

删除区间[$2,2$]代表的子串，得到字符串$abba$。

删除区间[$2,3$]代表的子串，得到字符串$aba$

删除区间[$3,3$]代表的子串，得到字符串$aaba$。

删除区间[$4,4$]代表的子串，得到字符串$aaba$。

删除区间[$4,5$]代表的子串，得到字符串$aab$。

删除区间[$5,5$]代表的子串，得到字符串$aabb$。

方案数共有$9$种。