首页 > 试题广场 >

字符串奇偶性问题

[编程题]字符串奇偶性问题
  • 热度指数：106 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\,\,\,\,\,\,\,\,\,\,对于长度为 m 的字符串 t_1t_2\cdots t_m，我们将字符串 f(t) 定义为以下内容的连接：
\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,● t 的全部奇数位，按字典序从小到大排序；
\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,● t 的全部偶数位，按字典序从大到小排序。
\,\,\,\,\,\,\,\,\,\,现在，对于长度为 n 的字符串 s_1s_2\cdots s_n ，你需要取出它的全部长度为 x 的子串，按照上方所述的步骤进行构造，能构造出多少个不相同的新字符串？

\,\,\,\,\,\,\,\,\,\,在本题中，字符的字典序即 \sf Ascii 码，即 \tt A < \cdots < Z < a < \cdots < z 。
\,\,\,\,\,\,\,\,\,\,如果字符串 t 可以通过从字符串 s 的开头删除若干（可能为零或全部）字符以及从结尾删除若干（可能为零或全部）字符得到，则字符串 t 是字符串 s 的子串。

输入描述:
\,\,\,\,\,\,\,\,\,\,每个测试文件均包含多组测试数据。第一行输入一个整数 T\ (1\le T\le 100) 代表数据组数，每组测试数据描述如下：

\,\,\,\,\,\,\,\,\,\,第一行上输入两个整数 n,x \left(1\le n \le 100;\ 1\le x \le n\right) 代表字符串长度、和询问长度。
\,\,\,\,\,\,\,\,\,\,第二行输入一个长度为 n ，且由大小写字母混合构成的字符串 s ，代表初始串。


输出描述:
\,\,\,\,\,\,\,\,\,\,对于每一组测试数据，在一行上输出一个整数，代表构造出的新字符串数量。
示例1

输入

2
5 4
bAbbb
6 3
nuhhhh

输出

2
3

说明

\,\,\,\,\,\,\,\,\,\,对于第一组测试数据，长度为 4 的不同子串有 \tt bAbb 和 \tt Abbb ：
\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,● 对于 \tt bAbb ，构造得到 f({\tt bAbb})={\tt bb} + {\tt bA} ；
\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,● 对于 \tt Abbb ，构造得到 f({\tt Abbb})={\tt Ab} + {\tt bb} 。
算法知识视频讲解
添加回答
牛客913834185号头像 牛客913834185号
t = int(input())
 
def build_f(t):
     
    odd = [t[i] fori in range(0, len(t), 2)]
    even = [t[i] fori in range(1, len(t), 2)]
    odd.sort()               
    even.sort(reverse=True) 
    return''.join(odd) + ''.join(even)
for_ in range(t):
    res = []
    n,x = map(int,input().split())
    s = input()
    fori in range(n-x+1):
        sub = build_f(s[i:i+x])
        ifsub not in res:
            res.append(sub)
    print(len(res))
发表于 2026-03-30 18:33:30 回复(0)
提交观点

问题信息

字符串 模拟 排序
来自：2024年秋招-蚂蚁集...
难度：
1条回答 236浏览

热门推荐

相关试题

字符串奇偶性问题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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