网站做外链多少钱手机网站乱弹

目录

牛客_小红的子串_滑动窗口+前缀和

题目解析

C++代码

Java代码

---

牛客_小红的子串_滑动窗口+前缀和

小红的子串

描述：
        小红拿到了一个长度为nnn的字符串，她准备选取一段子串，满足该子串中字母的种类数量在[l,r]之间。小红想知道，一共有多少种选取方案？

输入描述：

第一行输入三个正整数 n,l,rn,
第二行输入一个仅包含小写字母的字符串。
1 ≤ n ≤ 200000
1 ≤ l ≤ r ≤ 26

输出描述：

合法的方案数。

---

题目解析

        利用前缀和的思想，求种类个数在 [l, r] 区间内子串的个数，等于求 [1, r] 区间内个数 - [1, l - 1] 区间内个数。求种类个数在 [1, count] 区间内子串的个数，可以用滑动窗口来求解。

C++代码

#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;
}

Java代码

import java.util.*;
public class Main
{public static int n, l, r;public static char[] s;// 找出字符种类在 [1, x] 之间的⼦串的个数public static long find(int x){// 滑动窗⼝int left = 0, right = 0;int[] hash = new int[26];int kinds = 0; // 统计窗⼝内字符的种类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;}public static void main(String[] args){Scanner in = new Scanner(System.in);n = in.nextInt(); l = in.nextInt(); r = in.nextInt();s = in.next().toCharArray();System.out.println(find(r) - find(l - 1));}
}