1324C.md (2923B)
1 Source: https://codeforces.com/problemset/problem/1324/C 2 3 C. Frog Jumps 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 There is a frog staying to the left of the string $s = s_1 s_2 \ldots s_n$ consisting of $n$ characters (to be more precise, the frog initially stays at the cell $0$). Each character of $s$ is either 'L' or 'R'. It means that if the frog is staying at the $i$-th cell and the $i$-th character is 'L', the frog can jump only to the left. If the frog is staying at the $i$-th cell and the $i$-th character is 'R', the frog can jump only to the right. The frog can jump only to the right from the cell $0$. 22 23 Note that the frog can jump into the same cell twice and can perform as many jumps as it needs. 24 25 The frog wants to reach the $n+1$-th cell. The frog chooses some positive integer value $d$ before the first jump (and cannot change it later) and jumps by no more than $d$ cells at once. I.e. if the $i$-th character is 'L' then the frog can jump to any cell in a range $[max(0, i - d); i - 1]$, and if the $i$-th character is 'R' then the frog can jump to any cell in a range $[i + 1; min(n + 1; i + d)]$. 26 27 The frog doesn't want to jump far, so your task is to find the minimum possible value of $d$ such that the frog can reach the cell $n+1$ from the cell $0$ if it can jump by no more than $d$ cells at once. It is guaranteed that it is always possible to reach $n+1$ from $0$. 28 29 You have to answer $t$ independent test cases. 30 31 Input 32 33 The first line of the input contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases. 34 35 The next $t$ lines describe test cases. The $i$-th test case is described as a string $s$ consisting of at least $1$ and at most $2 \cdot 10^5$ characters 'L' and 'R'. 36 37 It is guaranteed that the sum of lengths of strings over all test cases does not exceed $2 \cdot 10^5$ ($\sum |s| \le 2 \cdot 10^5$). 38 39 Output 40 41 For each test case, print the answer — the minimum possible value of $d$ such that the frog can reach the cell $n+1$ from the cell $0$ if it jumps by no more than $d$ at once. 42 43 Example 44 45 Input 46 47 ``` 48 6 49 LRLRRLL 50 L 51 LLR 52 RRRR 53 LLLLLL 54 R 55 ``` 56 57 Output 58 59 ``` 60 3 61 2 62 3 63 1 64 7 65 1 66 ``` 67 68 Note 69 70 The picture describing the first test case of the example and one of the possible answers: 71 72  73 74 In the second test case of the example, the frog can only jump directly from $0$ to $n+1$. 75 76 In the third test case of the example, the frog can choose $d=3$, jump to the cell $3$ from the cell $0$ and then to the cell $4$ from the cell $3$. 77 78 In the fourth test case of the example, the frog can choose $d=1$ and jump $5$ times to the right. 79 80 In the fifth test case of the example, the frog can only jump directly from $0$ to $n+1$. 81 82 In the sixth test case of the example, the frog can choose $d=1$ and jump $2$ times to the right.