分数: 500 点
问题陈述
给你一个字符串 S 由大写英文字母组成。
高桥的目标是 增加 出现的次数 ABC 作为子串 S 正是 K,通过替换一些字符 S.
确定这是否可能,如果可以,找到高桥需要替换的最少字符数才能实现他的目标。
T 给出了测试用例;逐一解决。
“替换”是什么意思?
替换 1 个字符 S 表示选择一个整数 i 满意 1\leq i\leq \lvert S\rvert 并替换 i- 第一个字符 S 与任何 一 大写英文字母。
在这里, \lvert S\rvert 表示长度 S.
什么是子串?
的子串 S 是从开头和结尾删除零个或多个字符得到的字符串 S.
如果两个子字符串取自不同位置,则它们被视为不同的子字符串 S,即使它们作为字符串相等。
约束
- 1\leq T\leq 10^5
- S 是长度介于 3 和 3\times 10^5,包含在内,由大写英文字母组成。
- 1\leq K \leq 10
- 在每个输入中,总长度 S 所有测试用例最多 3\times 10^5.
- T 和 K 是整数。
输入
输入由标准输入按以下格式给出:
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
\mathrm{case}_i 代表 i- 第一个测试用例。
每个测试用例均按以下格式给出:
S K
输出
输出 T 行。
的 i第行 (1\leq i\leq T) 应包含以下问题的答案 i- 第一个测试用例。
对于每个测试用例,如果 Takahashi 不可能实现他的目标,则输出 -1;否则,输出达到他的目标需要替换的最少字符数。
示例输入 1
5 ATCABC 1 ABABC 1 XABCYZ 1 ZZZZZ 1 ABCBABCAEFCABAABC 2
示例输出 1
1 -1 6 3 3
在第一个测试用例中,给定的字符串 S=ATCABC 包含 ABC 作为子字符串一次。
替换第二个字符 S 与 B 给出 S=ABCABC,其中包含 ABC 作为子字符串两次。
因此,替换一个字符会增加出现的次数 ABC 作为子字符串 1,实现目标。因此,输出 1 在第一行。
在第二个测试用例中,给定的字符串 S=ABABC 包含 ABC 作为子字符串一次;无论角色如何 S 被替换,这是不可能的 S 包含 ABC 作为子字符串两次。
因此,输出 -1 在第二行。
在第三个测试用例中,给定的字符串 S=XABCYZ 包含 ABC 作为子字符串一次。
使 S 包含 ABC 作为子字符串两次,所有字符 S 必须更换,给予 S=ABCABC.
因此,输出 6 在第三行。