3154.子串简写-时间复杂度优化

解题思路：

开始直接使用暴力算法，两个嵌套循环进行搜索，时间复杂度为O(n^2)，这意味着对于非常长的字符串，程序需要执行大量的计算，效率低下。

我们可以通过以下步骤改进这个算法：

1.预处理: 遍历一遍字符串，预处理并保存每一个字符出现的位置。

2.滑动窗口: 使用双指针的策略，一个指针在找到c1后开始，另一个寻找c2，这样可以在O(n)的时间复杂度内完成。

3.快速统计: 一旦找到一个c2，我们知道所有在c1和这个c2之间的字符都能形成一个有效的子串。我们可以快速计算在当前c2之后有多少个c2，从而快速增加计数。

这里是改进后的代码：

#include <stdio.h>
#include <string.h>

int main() {
    int k;
    scanf("%d", &k);

    char s[500001];// 多一个'\0'
    char c1, c2;

    scanf("%s %c %c", s, &c1, &c2);

    int len = strlen(s); // strlen的时间复杂度为O(n),这里预处理
    long long count = 0; // 这里可能的子串数量可能非常大！要使用更大范围的整数类型（其余地方int就足够）    
    int c2_instances[len]; // 存储c2字符出现的位置
    int c2_count = 0; // c2字符的数量
    int i;

    // 预处理c2字符出现的位置
    for(i=0; i<len; ++i) {
        if (s[i]==c2) {
            c2_instances[c2_count++] = i;
        }
    }

    int j=0; // c2的索引

    for(i=0; i<len; ++i) {
        if(s[i]==c1) {
            // 寻找从当前c1开始，第一个位置大于等于i + k - 1的c2
            while(j<c2_count && c2_instances[j]< i+k-1) {
                ++j;
            }
            // 从当前c1开始，直到字符串末尾的c2都可以形成有效子串
            count += c2_count-j;
        }
    }

    printf("%lld", count);// 输出匹配ll类型的count
    return 0;
}

这个改进的代码的时间复杂度是O(n)，其中n是字符串的长度。预处理步骤和滑动窗口遍历都只需要单次遍历字符串，因此大大减少了计算量，并有助于避免超时。