题目描述

难度分:$1400$

输入$T(\leq 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 10^5$。

每组数据输入$n(1 \leq n \leq 10^5)$和长为$n$字符串$s$，只包含字符0到9。

输出$s$有多少个连续子串$t$，满足$t$中每个字符的出现次数，都不超过$t$中的字符种类数。

输入样例

7
1
7
2
77
4
1010
5
01100
6
399996
5
23456
18
789987887987998798

输出样例

1
2
10
12
10
15
106

算法

枚举

感觉这道题的做法还挺暴力的，就在超时的边缘，但提交上去跑得还挺快。注意到$s$串中只有0-9这$10$个数字，因此一个子串中最多就是$10$种数，每种数出现$10$次的话长度最大就是$100$。

因此，先预处理出每个数字在$s$串中出现次数的前缀和$presum[digit]$。对于长度为$1$的所有子串，肯定都满足要求，枚举长度在$[2,100]$的所有子串，对于任意一个子串$[l,r]$，遍历$[0,9]$中的所有整数，计算每个数字的频数，看是不是最大频数不超过数字种数即可。

复杂度分析

时间复杂度

预处理前缀和数组的时间复杂度为$O(n\Sigma)$，其中$\Sigma$表示字符集大小，本题中为$10$。后续枚举子串长度的时间复杂度为$min(n,100)$，滑动窗口的时间复杂度为$O(n)$，枚举数字的时间复杂度为$O(\Sigma)$，因此算法整体的时间复杂度为$O(min(n,100)n\Sigma)$。

空间复杂度

除去输入的字符串$s$，空间瓶颈在于前缀和数组$presum$。每个数字都有一个$O(n)$级别的前缀和数组，因此额外空间复杂度为$O(n\Sigma)$.

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 100010;
int t, n, presum[10][N];
char s[N];

void solve() {
    for(int digit = 0; digit <= 9; digit++) {
        for(int i = 1; i <= n; i++) {
            int d = s[i] - '0';
            presum[digit][i] = presum[digit][i - 1] + (d == digit? 1: 0);
        }
    }
    int ans = n;
    for(int len = 2; len <= min(n, 100); len++) {
        for(int r = len; r <= n; r++) {
            int l = r - len + 1, cnt = 0, mx = 0;
            for(int digit = 0; digit <= 9; digit++) {
                int t = presum[digit][r] - presum[digit][l - 1];
                if(t > 0) {
                    mx = mx < t? t: mx;
                    cnt++;
                }
            }
            if(mx <= cnt) ans++;
        }
    }
    printf("%d\n", ans);
}

int main() {
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        scanf("%s", s + 1);
        solve();
    }
    return 0;
}