1. 首页
2. 水题
3. 本页

HDU 5672 String (尺取法)

有一个明显的性质：如果子串$(i,j)$包含了至少$k$个不同的字符，那么子串$(i,k),(j<k<length)$也包含了至少$k$个不同字符。

因此对于每一个左边界，只要找到最小的满足条件的右边界，就能在$O(1)$时间内统计完所有以这个左边界开始的符合条件的子串。

寻找这个右边界，是经典的追赶法（尺取法,双指针法）问题。维护两个指针（数组下标），轮流更新左右边界，同时累加答案即可。复杂度 $O(length(S))$。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

char s[1000010];
int a[30];
int k;

int main() {
	int t;
	scanf("%d", &t);
	while (t--) {
		scanf("%s", s + 1);
		memset(a, 0, sizeof(a));
		scanf("%d", &k);
		//cout<<(s+1)<<endl;
		int len = strlen(s + 1);
		LL ans = 0;
		int cnt = 0;
		int j = 0;
		for (int i = 1; i <= len; ++i) {
			while (cnt < k && j + 1 <= len) {
				j++;
				a[s[j] - 'a']++;
				if (a[s[j] - 'a'] == 1) {
					cnt++;
				}
			}
			if (cnt == k) {
				ans += len - j + 1;
			}
			a[s[i] - 'a']--;
			if (a[s[i] - 'a'] == 0) {
				cnt--;
			}
		}
		cout << ans << endl;

	}

	return 0;
}