不会编程能建网站,电子商务网站建设购物车,seo引擎搜索入口,网站建设整改情况汇报目录
牛客_小红的子串_滑动窗口前缀和
题目解析
C代码
Java代码 牛客_小红的子串_滑动窗口前缀和
小红的子串
描述#xff1a; 小红拿到了一个长度为nnn的字符串#xff0c;她准备选取一段子串#xff0c;满足该子串中字母的种类数量在[l,r]之间。小红想知道前缀和
题目解析
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));}
}
