CF814C An impassioned circulation of affection

• 双指针
• 前缀和+双指针

双指针

用 $sum$ 维护区间 $(i, j),~0 \le i \le n$ 内非 $c$ 字符出现次数。

对于每一个 $i$：

• 当 $sum$ 等于 $m$ 时，停止右端点更新，此时右端点 $j$ 位于第 $m$ 个非 $c$ 字符之后；
• 若 $s_j = c$，则更新右端点，重复此操作，直到 $s_j \le c$；
• 至此，$(i, j-1)$ 即为以当前 $i$ 为做端点的最长合法区间，更新 $ans$;
• 更新左端点之前，根据 $s_i$ 是否为 $c$ 修改 $sum$。

时间复杂度为 $\mathcal{O}(n^2 q)$。

#include <cstdio>
#include <algorithm>

const int maxn = 1500 + 10;

int n;
char s[maxn];
int q;
int m;
char c;

int main() {
    scanf("%d", &n);
    scanf("%s", s);
    scanf("%d", &q);
    while (q--) {
        scanf("%d %c", &m, &c);
        int sum = 0;
        int ans = 0;
        for (int i = 0, j = i; i < n; i++) {
            for ( ; j < n && sum < m; j++) {
                if (s[j] != c) sum++;
            }
            while (s[j] == c) j++;
            ans = std::max(ans, j - i);
            if (s[i] != c) sum--;
        }
        printf("%d\n", ans);
    }
    return 0;
}

前缀和+双指针

与前面做法类似，通过维护前缀和的方式，实现快速获取 sum 的大小，免去每次询问计算过程。

时间复杂度为 $\mathcal{O}(n q)$。

#include <cstdio>
#include <algorithm>

const int maxn = 1500 + 10;

int n;
char s[maxn];
int q;
int m;
char c;

int pre[maxn][30];

int main() {
    scanf("%d", &n);
    scanf("%s", s);
    scanf("%d", &q);
    for (int i = 0; i < n; i++) {
        for (int j = 'a'; j <= 'z'; j++) pre[i][j - 'a'] = pre[i - 1][j - 'a'];
        pre[i][s[i] - 'a']++;
    }
    while (q--) {
        scanf("%d %c", &m, &c);
        int ans = 0;
        for (int i = 0, j = i; j < n; j++) {
            while ((j - i + 1) - (pre[j][c - 'a'] - pre[i - 1][c - 'a']) > m) i++;
            ans = std::max(ans, j - i + 1);
        }
        printf("%d\n", ans);
    }
    return 0;
}