PROBLEM LINK:
Setter: Abdullah Aslam
Tester: Michael Nematollahi
Editorialist: Taranpreet Singh
DIFFICULTY:
Simple
PREREQUISITES:
Basic observations, frequency array.
PROBLEM:
Given a string S, determine whether the given string is a dummy palindrome string or not.
A string is a dummy palindrome string (DPS) if we can arrange its characters in any order and then change any character to a different character such that the resulting string is a palindrome.
EXPLANATION
For the first subtask, string only contains the character ‘a’. So, if the given string is of even length, by changing character at any position, it becomes a non-palindrome, so even length string is not a DPS here. But if the given string is of odd length, we have the option to change the middle character, the resulting string being palindrome, hence odd length string for this subtask is a valid DPS.
Coming to final subtask now.
First of all, let us define a valid string as the string, whose characters can be arranged in any order to form a palindrome. So now, Our goal becomes to find out whether we can change exactly one character in string S to make it a valid string or not.
Consider two cases.
Length of S is even
In this case, a string is a valid string if, all the different characters in the string occur even number of times since for each position p, there is a position |S|-p+1 with the same character as position p. (Assumed one-based indexing).
Since we need to obtain a valid string after changing a character in S, String S should have exactly two characters with odd characters, so that we can just change one character to match the other one, resulting in a valid string, since after changing one character, frequency of both characters become even.
Note that if given S is a valid string of even length, It is not a DPS since it won’t remain valid string after changing one character.
Hence, string with exactly 2 distinct characters with odd frequency is a DPS.
Length of S is odd
In this case, a string is valid if all different characters in the string have even frequency except for the character occurring at the middle position. That is because the middle character occurs at the same position even if we reverse the string for checking palindrome.
If there’s only one character with odd frequency, we can change it to any other character, still ending up with only one character having an odd frequency. This character can be chosen as the middle character of palindrome, and thus, this type of string is also a DPS.
But there’s another possibility. Suppose there are three characters with odd frequency. We can change one of the characters to either of the remaining two and third character can be chosen as the middle character. So, a string with exactly 3 characters with odd frequency can also be made a valid string by changing exactly one character, thus, is a DPS.
Hence, all odd length strings with exactly 1 or 3
TIME COMPLEXITY
Time complexity is O(|S|+ A) per test case where A = 26 is the number of characters.
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define PB push_back
#define N 300101
#define SZ 3001
#define LB lower_bound
#define M 1000000007
#define UB upper_bound
#define MP make_pair
#define LD long double
#define F first
#define S second
int main()
{
LL k,i,j,lt,tc,d,r,q,y,z,v,x,m,n;
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>lt;
while(lt--)
{
LL fr[26]={0};
string s;
cin>>s;
n=s.length();
for(i=0;i<n;i++)
fr[s[i]-'a']++;
LL od=0;
for(i=0;i<26;i++)
if(fr[i]%2)
od++;
LL op=0;
if(n%2==0&&od==2)
op=1;
if(n%2==1&&(od==1||od==3))
op=1;
if(op)
{
cout<<"DPS"<<endl;
x++;
}
else
{
cout<<"!DPS"<<endl;
y++;
}
}
}
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define F first
#define S second
const int MAXN = 1e4 + 10;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int te; cin >> te;
while (te--){
int mask = 0;
string s;
cin >> s;
for (char c:s)
mask ^= 1<<int(c-'a');
int t = __builtin_popcount(mask);
if (s.size()&1) {
if (t <= 3)
cout << "DPS\n";
else
cout << "!DPS\n";
}
else {
if (t == 2)
cout << "DPS\n";
else
cout << "!DPS\n";
}
}
return 0;
}
Editorialist's Solution
import java.util.*;
import java.io.*;
class DPS{
//SOLUTION BEGIN
void pre() throws Exception{}
void solve(int TC) throws Exception{
String s = n();
int[] f = new int[26];
for(int i = 0; i< s.length(); i++)f[s.charAt(i)-'a']++;
int cnt = 0;
for(int i:f)if(i%2==1)cnt++;
if(s.length()%2==0){
if(cnt==2)pn("DPS");
else pn("!DPS");
}else{
if(cnt==1 || cnt==3)pn("DPS");
else pn("!DPS");
}
}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
static boolean multipleTC = true;
FastReader in;PrintWriter out;
void run() throws Exception{
in = new FastReader();
out = new PrintWriter(System.out);
//Solution Credits: Taranpreet Singh
int T = (multipleTC)?ni():1;
pre();for(int t = 1; t<= T; t++)solve(t);
out.flush();
out.close();
}
public static void main(String[] args) throws Exception{
new DPS().run();
}
int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
void p(Object o){out.print(o);}
void pn(Object o){out.println(o);}
void pni(Object o){out.println(o);out.flush();}
String n()throws Exception{return in.next();}
String nln()throws Exception{return in.nextLine();}
int ni()throws Exception{return Integer.parseInt(in.next());}
long nl()throws Exception{return Long.parseLong(in.next());}
double nd()throws Exception{return Double.parseDouble(in.next());}
class FastReader{
BufferedReader br;
StringTokenizer st;
public FastReader(){
br = new BufferedReader(new InputStreamReader(System.in));
}
public FastReader(String s) throws Exception{
br = new BufferedReader(new FileReader(s));
}
String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
st = new StringTokenizer(br.readLine());
}catch (IOException e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}
String nextLine() throws Exception{
String str = "";
try{
str = br.readLine();
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}
Feel free to Share your approach, if you want to. (even if its same 
) . Suggestions are welcomed as always had been. 
