A16829 | $Impost or Sus$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

一个由小写拉丁字母组成的字符串 $w$ 被称为可疑字符串，当且仅当同时满足以下所有条件： - 字母 $\mathtt{s}$ 至少出现两次，并且 - 对于每一个 $\mathtt{u}$ 的出现，它左、右两侧最近的两个 $\mathtt{s}$ 离这个 $\mathtt{u}$ 的距离必须相同。 在你完成字符串相关任务后，你的朋友 Aka 赠送给你一个只包含字母 $\mathtt{s}$ 和 $\mathtt{u}$ 的字符串 $r$。你可以对 $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$ 变为可疑字符串。

输入 #1

9
sus
uuuu
sssss
uusuuu
suuuuuu
usssssss
sssuuusss
susuusuuus
uuuuuuuuuuu

输出 #1

C++ 编辑器

输入

输出