logo AlgoBeat OnlineJudge
登录 注册

#104416. [BZOJ 4416] [Shoi2013]阶乘字符串

内存限制:256 MiB 时间限制:10000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

题目背景

(本题卡常数注意)

给定一个由前 个小写字母组成的串 。串 是阶乘字符串当且仅当前 个小写字母的全排列(共 种)都作为的子序列(可以不连续)出现。

由这个定义出发,可以得到一个简单的枚举法去验证,但是它实在太慢了。所以现在请你设计一个算法,在 秒内判断出给定的串是否是阶乘字符串。

输入格式

输入第 行一个整数 ,表示这个文件中会有 组数据。

接下来分 个块,每块 行:

  • 行一个正整数 ,表示 由前 个小写字母组成。
  • 行一个字符串

输出格式

对于每组数据,分别输出一行。每行是 YES 或者 NO,表示该数据对应的串 是否是阶乘字符串。

样例

样例输入 #1

2
2
bbaa
2
aba

样例输出 #1

NO
YES

数据范围与提示

第一组数据中,ab 这个串没有作为子序列出现。

测试点编号