#P18364. DNA Subsequences
DNA Subsequences
DNA Subsequences
题目描述
本题中的 DNA 字符串只由 A、C、G、T 四种字符组成。对于正整数 ,共有 个长度为 的 DNA 字符串。
如果这 个字符串全都是字符串 的子序列,就称 是 -rich 的。子序列不要求连续。
给定一个长度为 的 DNA 字符串 。对于每个 ,求最少需要修改 中多少个字符,才能使它变成 -rich 的字符串。如果不可能,答案为 。
每个 的答案独立计算;不同 之间不保留之前的修改。修改只改变字符,不改变字符串长度。
输入格式
第一行一个整数 。
第二行一个长度为 、仅由 A、C、G、T 组成的字符串 。
输出格式
输出 个整数。第 个整数表示使 变成 -rich 字符串所需修改字符数的最小值;不可能时输出 。
数据范围
- 。
- ,且 中只有
A、C、G、T。 - 每个输入文件只有一组数据。
样例输入 1
8
AAGTAGAA
样例输出 1
1 3 -1 -1 -1 -1 -1 -1
样例解释
当 时,可以只修改一个字符,得到 AAGTCGAA,使四种字符均出现。
当 时,可以修改三个字符,得到 CAGTTGAC。这个字符串包含所有长度为 2 的 DNA 字符串作为子序列。
CCGTTGAA 不能作为 时的目标,因为它不包含 AC 作为子序列。
当 时,无论怎样修改都无法满足要求。