Easy Subsequence Selection

All submissions for this problem are available.
### Read problem statements in [Hindi](http://www.codechef.com/download/translated/DEC19/hindi/SUBSPLAY.pdf), [Bengali](http://www.codechef.com/download/translated/DEC19/bengali/SUBSPLAY.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/DEC19/mandarin/SUBSPLAY.pdf), [Russian](http://www.codechef.com/download/translated/DEC19/russian/SUBSPLAY.pdf), and [Vietnamese](http://www.codechef.com/download/translated/DEC19/vietnamese/SUBSPLAY.pdf) as well. Chef has always been fond of girls, but he could not make any girl his friend. In order to finally make one, he was asked to solve the following problem: You are given a string $S$ with length $N$. Choose an integer $K$ and two nonempty subsequences $A$ and $B$ of characters of this string, each with length $K$, such that:  $A = B$, i.e. for each valid $i$, the $i$th character in $A$ is the same as the $i$th character in $B$.  Let's denote the indices of characters used to construct $A$ by $a_1, a_2, \ldots, a_K$, i.e. $A = (S_{a_1}, S_{a_2}, \ldots, S_{a_K})$. Similarly, let's denote the indices of characters used to construct $B$ by $b_1, b_2, \ldots, b_K$.  If we denote the number of common indices in the sequences $a$ and $b$ by $M$, then $M+1 \le K$. Since Chef is busy right now, he asks you to find the maximum value of $K$ such that it is possible to find sequences $A$ and $B$ which satisfy the given conditions or determine that there is no such $K$. ### Input  The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.  The first line of each test case contains a single integer $N$.  The second line contains a single string $S$ with length $N$. ### Output For each test case, print a single line containing one integer ― the maximum $K$, or $0$ if there is no solution. ### Constraints  $1 \le T \le 100$  $1 \le N \le 10^5$  $S$ contains only lowercase English letters ### Subtasks **Subtask #1 (20 points):** $N \le 8$ **Subtask #2 (80 points):** original constraints ### Example Input ``` 1 4 anxa ``` ### Example Output ``` 1 ```Author:  bhavyarustgi10 
Editorial  https://discuss.codechef.com/problems/SUBSPLAY 
Tags  bhavyarustgi10, dec19, melfice, simple, string, subsequence 
Date Added:  2102019 
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, rust, SCALA, swift, 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, SQL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions