All submissions for this problem are available.
Nemo went to the shop to buy a chain for his girlfriend. The shopkeeper has shown him a chain made of some expensive stones. The chain has n stones marked from 0 to n-1. The ith stone is connected with ((i+1)%n)th stone for each 0 ≤ i < n. Each stone can be either Ruby or Amber.
Nemo defines beauty factor B of a chain as the maximum number of consecutive stones of same type.
In the chain above, the beauty factor is B = 4 because there are 4 consecutive Amber in the chain.
Nemo wants to chose exactly one stone i and exchange it with a stone with different type. So if the ith stone is ruby, Nemo will exchange it with Amber and vice-versa. He wants to do it in such a way that the value B is as small as possible.
Given the configuration of the chain, can you find the minimum value of B that Nemo can get after exchanging exactly one stone? Note that, It’s not allowed to change positions of the stones, the new stone must be placed in the same position as the original stone.
First line contains number of test cases T (1 ≤ T ≤ 2500). For each test cases, there is a single line containing a string S (1 ≤ |S| ≤ 105) denoting the chain. Here |S| denotes the length or number of characters in the string. The string is made of only ’R’ (Ruby) and ’A’ (Amber). Total number of characters in the input file will be less than 5 x 106.
For each test case, print the case number and the answer in a single line. Look at the output for sample input for details.
2 RRRAAAARAA ARRRRAAAOutput for Sample Input
Case 1: 3 Case 2: 4
Case 1 represents the figure in the problem statement. Nemo can exchange one Amber with a Ruby and reduce B to 3.
|Tags||acm16kol, easy, kol_adm, string|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6|
Fetching successful submissions
If you are still having problems, see a sample solution here.