← 返回题目列表

Codeforces · 2178/B

B. 进口或 Sus

中文机器翻译题面 查看原题

由小写拉丁字母组成的字符串 $$$w$$$ 称为 可疑 当且仅当满足以下所有条件时:

  • 字母 $$$\mathtt{s}$$$ 至少出现两次,并且
  • 对于每次出现的字母 $$$\mathtt{u}$$$,最近出现的两个 $$$\mathtt{s}$$$ 距 $$$\mathtt{u}$$$ 的字符数相同。

在看到你完成一个字符串任务后,你的朋友 Aka 送给你一个字符串 $$$r$$$,仅由字母 $$$\mathtt{s}$$$ 和 $$$\mathtt{u}$$$ 组成。您可以对$$$r$$$执行以下操作:

  • 选择索引 $$$i$$$ ($$$1\le i\le |r|$$$),并将 $$$r_i$$$ 设置为 $$$\mathtt{s}$$$。

确定生成 $$$r$$$ 所需的最少操作数 可疑。可以证明,在给定的约束下,总是可以将 $$$r$$$ 转换为 可疑 字符串。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的唯一行包含字符串 $$$r$$$ ($$$3\le |r|\le 2\cdot 10^5$$$)。保证 $$$r_i = \mathtt{s}$$$ 或 $$$\mathtt{u}$$$。

保证所有测试用例的 $$$|r|$$$ 总和不超过 $$$2\cdot 10 ^ 5$$$。

输出

对于每个测试用例,输出一个整数 - 生成 $$$r$$$ 所需的最少操作数 可疑.

示例

输入
复制

9
sus
uuuu
sssss
uusuuu
suuuuuu
usssssss
sssuuusss
susuusuuus
uuuuuuuuuuu

输出
复制

0
3
0
3
3
1
1
2
6

注意

在第一个测试用例中,字符串 $$$\mathtt{sus}$$$ 已经是 可疑 因为 $$$\mathtt{s}$$$ 在字符串中出现了两次,并且距离唯一的 $$$\mathtt{u}$$$ 最近的两个 $$$\mathtt{s}$$$ 距离都为 $$$1$$$ 个字符: $$$\color{红色}{\mathtt{s}}\下划线{\mathtt{u}}\color{红色}{\mathtt{s}}$$$。

在第二个测试用例中,最好对索引 $$$1$$$、$$$3$$$ 和 $$$4$$$ 执行操作。之后,字符串 $$$s$$$ 变为 $$$\texttt{suss}$$$。字符串 $$$\mathtt{suss}$$$ 是 可疑 因为 $$$\mathtt{s}$$$ 在字符串中出现了 $$$3$$$ 次,并且距离唯一的 $$$\mathtt{u}$$$ 距离最近的两个 $$$\mathtt{s}$$$ 都相距 $$$1$$$ 个字符: $$$\color{红色}{\mathtt{s}}\下划线{\mathtt{u}}\color{红色}{\mathtt{s}}\mathtt{s}$$$。

在第三个测试用例中,$$$\mathtt{u}$$$ 的条件空为真,因为字符串 $$$\mathtt{sssss}$$$ 中没有 $$$\mathtt{u}$$$。因此,给定的字符串已经是 可疑.

在第六个测试用例中,初始字符串 $$$\mathtt{usssssss}$$$ 是 不 可疑 因为距离唯一的 $$$\mathtt{u}$$$ 最近的两个 $$$\mathtt{s}$$$ 分别相距一和两个字符:$$$\underline{\mathtt{u}}\color{red}{\mathtt{ss}}\mathtt{sssss}$$$。