← 返回题目列表

Codeforces · 1324/C

C. 青蛙跳

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

有一只青蛙停留在由 $$$n$$$ 个字符组成的字符串 $$$s = s_1 s_2 \ldots s_n$$$ 的左侧(更准确地说,青蛙最初停留在单元格 $$$0$$$ 处)。 $$$s$$$ 的每个字符都是“L”或“R”。这意味着如果青蛙停留在第 $$$i$$$ 个单元格并且第 $$$i$$$ 个字符是“L”,则青蛙只能跳到左侧。如果青蛙停留在第 $$$i$$$ 个单元格且第 $$$i$$$ 个字符是“R”,则青蛙只能跳到右侧。青蛙只能从单元格 $$$0$$$ 跳到右侧。

请注意,青蛙可以跳进同一个单元格两次,并且可以根据需要执行多次跳跃。

青蛙想要到达第 $$$n+1$$$ 个单元格。青蛙在第一次跳跃之前选择一些正整数值$$$d$$$(以后不能更改它),并且一次跳跃不超过$$$d$$$个单元格。 IE。如果第 $$$i$$$ 个字符是“L”,则青蛙可以跳转到 $$$[max(0, i - d); 范围内的任何单元格; i - 1]$$$,如果第 $$$i$$$ 个字符是“R”,则青蛙可以跳转到 $$$[i + 1; 范围内的任何单元格;分钟(n + 1; i + d)]$$$。

青蛙不想跳太远,所以你的任务是找到 $$$d$$$ 的最小可能值,这样青蛙可以从 $$$0$$$ 单元格到达 $$$n+1$$$ 单元格,前提是它一次可以跳过不超过 $$$d$$$ 个单元格。保证总是可以从$$$0$$$到达$$$n+1$$$。

您必须回答 $$$t$$$ 独立测试用例。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

接下来的 $$$t$$$ 行描述测试用例。第 $$$i$$$ 测试用例被描述为字符串 $$$s$$$,由至少 $$$1$$$ 和最多 $$$2 \cdot 10^5$$$ 字符“L”和“R”组成。

保证所有测试用例的字符串长度总和不超过 $$$2 \cdot 10^5$$$ ($$$\sum |s| \le 2 \cdot 10^5$$$)。

输出

对于每个测试用例,打印答案 - $$$d$$$ 的最小可能值,使得青蛙可以从单元格 $$$0$$$ 到达单元格 $$$n+1$$$(如果它一次跳跃不超过 $$$d$$$)。

示例

输入 #1

6
LRLRRLL
L
LLR
RRRR
LLLLLL
R

输出 #1

3
2
3
1
7
1

注意

该图片描述了示例的第一个测试用例以及可能的答案之一:

在示例的第二个测试用例中,青蛙只能直接从 $$$0$$$ 跳到 $$$n+1$$$。

在示例的第三个测试用例中,青蛙可以选择$$$d=3$$$,从单元格$$$0$$$跳转到单元格$$$3$$$,然后从单元格$$$3$$$跳转到单元格$$$4$$$。

在示例的第四个测试用例中,青蛙可以选择 $$$d=1$$$ 并向右跳 $$$5$$$ 次。

在示例的第五个测试用例中,青蛙只能直接从$$$0$$$跳到$$$n+1$$$。

在示例的第六个测试用例中,青蛙可以选择 $$$d=1$$$ 并向右跳 $$$2$$$ 次。