QTOO_2523 - Editorial

editorial
,
#1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: moonlight_cl25
Testers: iceknight1093, rivalq
Editorialist: iceknight1093

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)
1 Like
#2

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;
}
#3

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