时间复杂度最低方法

解题思路:

1.直接暴力遍历出c1,c2的位置数组,以及c1,c2的数量。

2.遍历c1,c2数组，用双循环，每一个c1第一次匹配成功c2后边的c2是一定可以匹配这个c1的，时记录该c2的位置，并且下一个c1直接从该位置开始匹配c2.

参考代码:

#include<bits/stdc++.h>
using namespace std;
#define int long long          //这里注意一定要开long long因为字符串长在5*10^5级别!!
signed main()
{
    int k;
    int num=0;
    char str[500001];          //预留一位存放\0
    char start,end;            //也就是c1 c2
    scanf("%lld %s %c %c",&k,&str,&start,&end);
    int len=0;                 //求字符串长
    while(str[len]!='\0')
    {
        len++;
    }
    int startl[len],endl[len];  //存放c1和c2
    int l=0;                    //定义c1和c2的个数
    int j=0;
    for(int i=0;i<len;i++)      //填充c1 c2数组
    {
        if(str[i]==start)
        {
            startl[j]=i;
            j++;
        }
        if(str[i]==end)
        {
            endl[l]=i;
            l++;
        }
    }
    int oo[len]={0};            //oo数组记录离当前c1最近的c2,即oo[0],下一个c1匹配c2即可直接从oo[0]开始遍历c2
    for(int i=0;i<j;i++)
    {
        int oi=0;
        for(int i2=oo[0];i2<l;i2++)
        {
            if(endl[i2]-startl[i]+1>=k)   //如果子串长度大于等于k即为匹配成功
            {
                oo[oi]=i2;
                oi++;
                
                num+=l-i2;                //如果该c2匹配成功则说明后面的c2肯定是子串长大于k的，也一定能匹配上
                                          //所以就不用遍历后边的c2,直接加上去并且break以降低时间复杂度。
                break;
            }
        }
    }
    printf("%lld",num);                   //注意输出格式为lld;
}