IITWPC4H - Maggu and Cuteness of Strings

no tags 

Given two strings s and t of size n and m respectively. You can construct a string w of size n+m using s and t such that it should contain both s and t as its subsequences.
           
String w must satisfy this condition: For each character from 'a' to 'z', count of the character in w should be equal to sum of count in s and t. Additionally every character of w must belong to the subsequence for either s or t. 

eg. if s = ab and t = cd, Then w can be abcd, acbd, cdab, cabd, acdb, cadb. Note that adcb is not correct, As t is not a subsequence in it.

“Cuteness value” of a string is defined as the maximum length of consecutive equal characters in the string.

For all possible string w that you can construct, find out the maximum value of “Cuteness value”.

Input 

First line contains T: number of test cases

For each test you case you are given a single line containing two space separated strings s and t. (1 <= size (s), size (t) <= 10^5).

Both the strings s and t will have characters from 'a' to 'z' of English alphabet only.

Note:Sum of length of all the input string is less than 5*10^6.

Output

For each test case, output the answer as given in problem statement.

Example

Input:
1
ab ab Output: 2

hide comments
vivek_dwivedi: 2018-06-15 19:05:30

question is easy af! did it in o(n). dont know how people solved in 0.0!!

dark_lord1: 2016-03-31 16:34:56

Extremely easy problem..Don't think complex, keep it simple..No DP..
Note : The strings may contain characters other than 'a-z' but not white spaces

anonymous: 2014-03-03 06:49:23

Last edit: 2014-03-21 19:34:40
aqfaridi: 2014-03-03 06:49:23

WTF .. s and t can contain other characters too. [cause me many RE :( ](@praveen123 modify the problem statement)

Jumpy: 2014-03-03 06:49:23

easy if you think simple and be aware of boundary conditions

Akhilesh Anandh: 2014-03-03 06:49:23

Agree with fitcat.. it gave me a runtime error

fitcat: 2014-03-03 06:49:23

@PS:
The problem description "Both the strings s and t will have characters from 'a' to 'z' of English alphabet only." is not true. Either or both contain(s) other characters. This is verified by my test account (test). Please fix it.

yashag: 2014-03-03 06:49:23

My submission id is 11022017.
It is working for all the possible test cases i've tried (i.e. more than 50), yet it shows WA on spoj. Please give me a test case where my code goes wrong...

Sameer: 2014-03-03 06:49:23

Don't use string in c++.. costed me 2 WA's :( :)

Kevin Sebastian: 2014-03-03 06:49:23

any tricky test cases?


Added by:praveen123
Date:2014-02-03
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:IITK ACA CSE online judge