牛客对应题目链接:小红的子串 (nowcoder.com)
一、分析题目
利用前缀和的思想,求种类个数在 [l, r] 区间内子串的个数,等于求 [1, r] 区间内个数 - [1, l - 1] 区间内个数。
求种类个数在 [1, count] 区间内子串的个数,可以用滑动窗口来求解。
二、代码
//值得学习的代码
#include <iostream>
#include <string>using namespace std;int n, l, r;
string s;// 找出字符种类在 [1, x] 之间的⼦串的个数
long long find(int x)
{if(x == 0) return 0;// 滑动窗⼝int left = 0, right = 0;int hash[26] = { 0 }, kinds = 0; // 统计窗⼝内字符种类的个数long long ret = 0;while(right < n){if(hash[s[right] - 'a']++ == 0) kinds++;while(kinds > x){if(hash[s[left] - 'a']-- == 1) kinds--;left++;}ret += right - left + 1;right++;}return ret;
}int main()
{cin >> n >> l >> r >> s;cout << find(r) - find(l - 1) << endl;return 0;
}
三、反思与改进
想到了滑动窗口,但是一直想不明白其中一类子串要如何计算,原来是得配合前缀和使用。