SUBPAL - Gyanbabas Admission Test

no tags 

Gyanbaba is the wisest saint of the universe. People from all over the world come to him to seek gyan (knowledge). But he does not offer his wisdom to everyone. He choses the right person to give wisdom after taking a test, his murids (apprentices) call this Gyanbaba's Admission Test. For the admission test Gyanbaba writes down a string containing lowercase English letters only and asks the applicants to find the substring of maximum length, the characters of which can be permuted to create a palindrome. Can you pass his test?

Input

Input starts with an integer T (≤ 30), denoting the number of test cases.

Each case has a string S, the string Gyanbaba chose. You can assume 1 ≤ length(S) ≤ 100000.

Output

For each case print one line containing the case number starting with 1 and the length of the substring, which satisfies Gyanbaba's query.

Example

Input:
2
abcfebcbbcbd
fesdddssefseefs

Output:
Case 1: 7
Case 2: 13

hide comments
Baojun Wang: 2016-03-03 09:15:19

semi brute force passed.

Alex Anderson: 2015-10-27 04:35:39

I wouldn't really call that O(N)

ashish22_dwd: 2015-10-16 20:41:15

Can u check and tell, which test cases are not getting passed by my program.. what is wrong with my solution.. submission id is 15385610

snehil10111995: 2015-09-28 09:01:23

Ant tricky test cases? I am getting WA. I have no idea why. Tried all test cases which I can think of.

saurajit: 2015-09-24 09:12:28

My id is 15197379 Why am i getting WA i think my prog is correct

Sourav Sen Tonmoy: 2015-09-22 10:31:36

maverick_10, for the first sample case, you can take the substring "bcbbcbd" and permute it to make "bbcdcbb", which is a palindrome. You cannot do this for any other substring of greater length. As a result, the answer is "bcbbcbd".size() or 7. Hope it helps.

Sourav Sen Tonmoy: 2015-09-22 10:28:26

Lu Qi, I initially increased the time limit for Java and Python users. Thanks for pointing out the flaw. I've decreased the time limit and rejudged all the solutions. This problem can be solved in O(n) time with higher memory, but I intended to let O(nlogn) solutions with less memory pass. Otherwise it can be solved in under a second. Try optimizing the solution.

Sushant Gupta: 2015-09-21 21:13:29

My submit id is: 15177371 . Can you tell me why is it giving WA. I think my program is correct.

maverick_10: 2015-09-21 16:51:35

Please provide explanation for sample input - output .

Lu Qi: 2015-09-21 15:07:44

The test cases is so weak. The brute force algorithm can solve this problem. @Sourav Sen Tonmoy see the submit id: 15172562.

Last edit: 2015-09-21 15:08:06

Added by:Sourav Sen Tonmoy
Date:2015-09-18
Time limit:5.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:Own problem. Used in University of Dhaka internal contest 2015, for 1st and 2nd year only.