蓝桥杯2023年第十四届省赛真题-子串简写

解题思路:
分别记录首字母和尾字母出现的位置，然后遍历数组得出结果。
注意事项:
降低时间复杂度,不走回头路，时间复杂度由O(n²)降为O(n)。
参考代码:

#include <stdio.h>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main(){
  int k;
  scanf("%d", &k);
  string s;
  cin >> s;
  char a,b;
  getchar();
  scanf("%c", &a);
  getchar();
  scanf("%c", &b);
  long long res = 0;
  vector<int> start, end;
  for(int i = 0; i < s.size(); i++){
    if(s[i] == a){
      start.push_back(i);
    }
    if(s[i] == b){
      end.push_back(i);
    }
  }
  int tmp = 0;
  for(int i = 0; i < start.size(); i++){
    for(int j = tmp; j < end.size(); j++){
      if(end[j] - start[i] < k-1){
        continue;
      }else{
        res += end.size() - j;
        tmp = j;
        break;
      }
    }
  }
  printf("%lld", res);
  return 0;
}