Find The Key
All submissions for this problem are available.
Owlman wants to destroy the earth. Batman come to the rescue. Owlman has planted a bomb having the power to destroy earth. To diffuse the bomb Batman need to solve a puzzle.
Batman need to enter a password to diffuse the bomb. There are only two button on the keypad, A and B. Batman is also given a n length string consisting of only these two characters. There was a leak in the Owlman's team and he tells Batman the first step toward getting the password is to concatenate the string to itself to generate a string of 2n length. Batman knew that owlman loves owlfunction().Owlfuncton is defined as
For a string of length 2n. Consider all substring of length less than or equal to n that ends on position i for 1<=i<=2n
owlfunction(i) = smallest owlographic substring over all such substring
If X is proper prefix of Y then X is said to be owlographically greater than Y otherwise consider owlographic as lexicographic.Since Batman is very smart he figured out that password would be the smallest i for which owlfunction(i) is longest.
First line contains an integer T denoting the number of test cases. For each test case:
- First line contains a integer n denoting the length of string
- Second line contains a n length string
For each test case:
- Output the password in newline
- Summation of n over all test cases <=150,000
Input: 2 2 AA 2 AB Output: 2 2
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions