 # QTOO_2523 - Editorial

Author: moonlight_cl25
Testers: iceknight1093, rivalq
Editorialist: iceknight1093

TBD

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]++;
}

for (int i = 1; i <= 26; i++)
{
if (frq[i] > 1)
{
break;
}
}

}
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)

1 Like

Why i am getting wrong answer here?

#include <bits/stdc++.h>
using namespace std;

int32_t main() {
int t;
cin>>t;
while(t--){
int n;
cin>>n;
string s;
cin>>s;
map<char, int> m;
for(int i = 0; i < n; i++){
m[s[i]]++;
}
string p;
int ans = 0;
int mie = INT_MAX, mio = INT_MAX;
for(auto pr : m){
if(pr.second & 1){
mio = min(mio, pr.second);
}else{
mie = min(mie, pr.second);
}
}
if((mie > 1 && mie != INT_MAX) || (mio > 1 && mio != INT_MAX)){
cout<<n-2<<"\n";
}else{
cout<<-1<<"\n";
}
}
return 0;
}


Consider the input

1
4
abbb


you print -1 which is wrong.

That code would work if you used max instead of min (but the intended solution is simpler).

1 Like