# PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Contest: Division 3

Contest: Division 4

* Author:* moonlight_cl25

*iceknight1093, rivalq*

**Testers:***iceknight1093*

**Editorialist:**# DIFFICULTY:

TBD

# PREREQUISITES:

None

# PROBLEM:

Given a string, find the maximum number of characters that can be deleted from it so that the remaining characters form a palindrome of length at least 2.

Print -1 if this is not possible.

# EXPLANATION:

Any palindrome of length \geq 2 has at least one pair of repeated characters, since the first character equals the last.

This tells us that:

- If S contains at least two occurrences of the same character, the answer is N-2. This is because we can create a palindrome of length 2 by deleting everything else.
- If S doesn’t contain repeated characters, the answer is -1 since creating a palindrome of length \geq 2 is impossible.

So, the only check that needs to be done is whether S contains repeated characters or not.

This can be done in \mathcal{O}(N), or even in \mathcal{O}(N^2) by iterating across all pairs of characters and checking whether they’re equal; since N is small enough.

# TIME COMPLEXITY

\mathcal{O}(N) per test case.

# CODE:

## Setter's code (C++)

```
#include <iostream>
#include <vector>
using namespace std;
void solve()
{
vector<int> frq(27);
int n;
string s;
cin >> n >> s;
for (int i = 0; i < n; i++)
{
frq[s[i] - 96]++;
}
int answer = -1;
for (int i = 1; i <= 26; i++)
{
if (frq[i] > 1)
{
answer = n - 2;
break;
}
}
cout << answer << endl;
}
int main()
{
int tc;
cin >> tc;
while (tc--)
{
solve();
}
return 0;
}
```

## Editorialist's code (Python)

```
for _ in range(int(input())):
n = int(input())
s = sorted(input())
for i in range(n-1):
if s[i] == s[i+1]:
print(n-2)
break
else:
print(-1)
```