#P18364. DNA Subsequences

DNA Subsequences

DNA Subsequences

题目描述

本题中的 DNA 字符串只由 A、C、G、T 四种字符组成。对于正整数 kk,共有 4k4^k 个长度为 kk 的 DNA 字符串。

如果这 4k4^k 个字符串全都是字符串 ss 的子序列,就称 ss 是 kk-rich 的。子序列不要求连续。

给定一个长度为 nn 的 DNA 字符串 ss。对于每个 k=1,2,…,nk=1,2,\ldots,n,求最少需要修改 ss 中多少个字符,才能使它变成 kk-rich 的字符串。如果不可能,答案为 −1-1。

每个 kk 的答案独立计算;不同 kk 之间不保留之前的修改。修改只改变字符,不改变字符串长度。

输入格式

第一行一个整数 nn。

第二行一个长度为 nn、仅由 A、C、G、T 组成的字符串 ss。

输出格式

输出 nn 个整数。第 kk 个整数表示使 ss 变成 kk-rich 字符串所需修改字符数的最小值;不可能时输出 −1-1。

数据范围

  • 1≤n≤2000001\le n\le200000。
  • ∣s∣=n|s|=n,且 ss 中只有 A、C、G、T。
  • 每个输入文件只有一组数据。

样例输入 1

8
AAGTAGAA

样例输出 1

1 3 -1 -1 -1 -1 -1 -1

样例解释

当 k=1k=1 时,可以只修改一个字符,得到 AAGTCGAA,使四种字符均出现。

当 k=2k=2 时,可以修改三个字符,得到 CAGTTGAC。这个字符串包含所有长度为 2 的 DNA 字符串作为子序列。

CCGTTGAA 不能作为 k=2k=2 时的目标,因为它不包含 AC 作为子序列。

当 k>2k>2 时,无论怎样修改都无法满足要求。