首页 > 试题广场 >

重排的回文串

[编程题]重排的回文串

给一个长为 n 的只含小写字母的字符串

每次查询一个区间 [l,r] 内，有多少子区间可以重排为一个回文串

一个区间可以重排为一个回文串：

就是说我们可以以一定顺序排列这个区间内的所有数使得排列后为一个回文串



输入描述:
第一行两个正整数n,m
第二行一个长为 n 的字符串
之后 m 行每行两个数 l 和 r


输出描述:
对于每个询问，输出一个整数表示答案
示例1

输入

6 5
zzqzzq
2 4
3 4
2 3
4 5
1 1

输出

4
2
2
3
1

说明

[2,4]为zqz,其中[2,2],[3,3],[4,4],[2,4]都可以重排为一个回文串
[3,4]为qz,其中[3,3],[4,4]可以重排为一个回文串
[2,3]为zq,其中[2,2],[3,3]可以重排为一个回文串
[4,5]为zz,其中[4,4],[5,5],[4,5]可以重排为一个回文串
[1,1]为z,只有这一个区间且其可以重排为一个回文串

备注:
对于100%的数据，有n , m <= 60000
算法知识视频讲解
添加回答

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

莫队
上传者：牛客301599号
难度：
0条回答 0浏览

热门推荐

通过挑战的用户

查看代码

相关试题

重排的回文串

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号