Bi_lindrome!

Difficulty Rating:1095            @Codechef

Problem

You are given a string $�$ of length $�$.

Your task is to delete a subsequence of maximum length from the string, such that, after concatenating the remaining parts of the string, it becomes a palindrome of length greater than $1$.

If this is possible, print the maximum length of the subsequence that can be deleted. Otherwise, print $-1$.

Input Format

• The first line of input will contain a single integer $�$, denoting the number of test cases.
• Each test case consists of $2$ lines of input:
  • The first line consists the a single integer $�$ - the length of string $�$.
  • The second line contains string $�$, consisting of lowercase english alphabets.

Output Format

For each test case, if it is possible to delete a subsequence under the given conditions, print a single integer, denoting the maximum length of the subsequence that can be deleted. Otherwise, print $-1$.

Constraints

• $1\le �\le 2500$
• $3\le �\le 100$
• $�$ consists of lowercase english alphabets.

Sample 1:

Input                                           Output

3      
                                                              
6
babkhj                                                4

3 
abc                                                    -1

4 
qtoo                                                    2

Explanation:

Test case $1$: Possible ways to delete a subsequence are:

• Delete subsequence khj to get palindrome bab.
• Delete subsequence akhj to get palindrome bb.

The subsequence having maximum length that can be deleted is akhj, having length $4$.

Test case $2$: We cannot delete any subsequence under the given conditions.

Test case $3$: We can delete the subsequence qt to obtain the string oo, which is a palindrome. This is the only subsequence that can be deleted and it has length $2$.

           Solution:-

#include <iostream>

using namespace std;

#include<bits/stdc++.h>

int main() {

// your code goes here

int t;

cin>>t;

while(t--){

    int n;

    string s;

    cin>>n;

    cin>>s;

    bool c=false;

    unordered_map<char,int>m;

    for(int i=0;i<s.length();i++){

        m[s[i]]++;

    }

    for(auto i:m){

        if(i.second>=2){

            c=true;

        }

    }

    if(c)

    cout<<(s.length()-2)<<endl;

    else

    cout<<"-1"<<endl;

}

return 0;

}