HDU 5672 String

这道题是之前POJ这道题的弱化版本。

这应该是第五道尺取了吧，有点感觉了。

只要看出尺取可做，就是水题。

题意：
给你一个字符串，问你有多少个子串至少含有k个不同的字母。

思路：
恩。因为字符串的元素全都是字母，也就是上面poj里将数字限制在里0～25，是一样的做法。
但是这道题并没有要求最少，也就是一旦一个字符串符合要求，往后的所有子串都符合要求。累加即可。

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;

typedef long long ll;
const int inf = 0x3f3f3f3f;
const double eps = 1e-5;
const int maxn = 1e6 + 5;
const int mod = 1e9 + 7;

char str[maxn];
int num[30];

int main()
{
    int T, k;
    scanf("%d", &T);
    while (T--) {
        scanf("%s %d", str, &k);
        int len = strlen(str), ch_num = 0;
        ll ans = 0;
        fill(num, 0);
        for (int i = 0, j = 0; i < len; i++) {
            while (ch_num < k && j < len) {
                if (num[str[j++] - 'a']++ == 0)
                    ch_num++;
            }
            if (ch_num < k)
                break;
            ans += (len - j + 1LL);
            if (--num[str[i] - 'a'] == 0)
                ch_num--;
        }
        printf("%lld\n", ans);
    }
    return 0;
}