In this HackerEarth One Swap to Palindrome problem solution, You are given T tasks to perform. In each task, you are given a string S of length N. You are allowed to select any two indices i and j (i!=j) of the given string and perform exactly one swap between the characters at these indices.

If it is possible to make the new string a palindrome then print "Yes", else print "No".


HackerEarth One Swap to Palindrome problem solution


HackerEarth One Swap to Palindrome problem solution.

#include<bits/stdc++.h>
#define PI acos(-1.0)
#define X first
#define Y second
#define mpp make_pair
#define nl printf("\n")
#define SZ(x) (int)(x.size())
#define pb(x) push_back(x)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define S(a) scanf("%d",&a)
#define P(a) printf("%d",a)
#define SL(a) scanf("%lld",&a)
#define S2(a,b) scanf("%d%d",&a,&b)
#define SL2(a,b) scanf("%lld%lld",&a,&b)
#define all(v) v.begin(),v.end()
#define CLR(a) memset(a,0,sizeof(a))
#define SET(a) memset(a,-1,sizeof(a))
#define fr(i,a,n) for(int i=a;i<=n;i++)
using namespace std;
typedef long long ll;
#define MX 200005
#define inf 100000001LL
#define MD 1006000007LL
#define eps 1e-9

int main() {
freopen("input8.txt","r",stdin);
freopen("output8.txt","w",stdout);
int tc;
cin>>tc;
while(tc--) {
string s;
cin>>s;
int n=s.size();
int l=0,r=n-1;
char a,b,c,d;
int cnt=0;
while( l<r ) {
if( s[l]!=s[r] ) {
cnt++;
if( cnt==1 ) {
a=s[l],b=s[ r ];
} else if( cnt==2 ) {
c=s[l],d=s[ r ];
} else break;
}
l++,r--;
}
//cout<<cnt<<endl;
if( cnt>2 ) cout<< "No\n";
else if( cnt==2 ) {
if( (a==c && b==d) || (a==d && c==b) ) cout<< "Yes\n";
else cout<< "No\n";
} else if( cnt==1 ) {
if( n%2==0 )cout<< "No\n";
else if( s[n/2]==a || s[n/2]==b ) cout<< "Yes\n";
else cout<< "No\n";
} else cout<< "Yes\n";
}

return 0;
}

Second solution

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

#include<limits>
#define ll long long

#define y0 sdkfaslhagaklsldk
#define y1 aasdfasdfasdf
#define yn askfhwqriuperikldjk
#define j1 assdgsdgasghsf
#define tm sdfjahlfasfh
#define lr asgasgash
#define norm asdfasdgasdgsd
#define have adsgagshdshfhds

#define debugdec int deb=1;
#define debug() cout<<"real_flash>> "<<(deb++)
#define pb push_back
#define mk make_pair
#define MEM(a,b) memset(a,(b),sizeof(a))
#define TEST int test; cin >> test;while(test--)
#define si(x) scanf("%d",&x)
#define author real_flash
#define rep(p,q,r) for(int p=q;p<r;p++)
#define repr(p,q,r) for(int p=q;p>=r;p--)
#define repit(it, a) for(__typeof(a.begin()) it = a.begin();it != a.end(); ++it)
#define si2(x,y) scanf("%d %d",&x,&y)
#define si3(x,y,z) scanf("%d %d %d",&x,&y,&z)
#define FIND(x,y) x.find(y)==x.end()
#define sl(x) scanf("%lld",&x)
#define prl(x) printf("%lld\n",x)
#define ff first
#define ss second
#define BE(a) a.begin(), a.end()
#define bitcnt(x) __builtin_popcountll(x)
#define INF 111111111111111LL
#define mo 1000000007
#define PI 3.141592653589793

typedef pair<int, int > pii;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef pair<ll, ll> pll;

template<class T> inline T gcd(T a, T b) { while(b) b ^= a ^= b ^= a %= b; return a;}

//std::cout << std::setprecision(3) << std::fixed;
int MAX=numeric_limits<int>::max();
const int N=1e6+5;
//ios_base::sync_with_stdio(0);cin.tie(0);

int n;
string s;
pair<char ,char >pp[10];
int p=0;


int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
//freopen("D:/progs/output.txt", "w", stdout);
#endif
TEST
{
// s="";
p=0;
// cin>>s;
assert((cin>>s));
n=s.length();
assert(n>=1&&n<=1e5);
rep(i,0,n)
{
assert(s[i]>='a'&&s[i]<='z');
}



if(n==1)
{
cout<<"Yes\n";
continue;
}
int f=1;
for(int i=0,j=n-1;i<n/2;i++,j--)
{
if(s[i]!=s[j])
{
pp[p++]=mk(s[i],s[j]);
}
if(p>2)
{
f=0;
cout<<"No\n";
break;
}
}
//cout<<p<<"\n";
if (f==0)
continue;
else if(p==0)
{
cout<<"Yes\n";

}
else if(p==2)
{
if((pp[0].ff==pp[1].ss && pp[1].ff==pp[0].ss)||(pp[0].ff==pp[1].ff && pp[0].ss==pp[1].ss))
{
cout<<"Yes\n";
}
else cout<<"No\n";

}
else
{
if(n%2==1 && (s[n/2]==pp[0].ff||s[n/2]==pp[0].ss))
{
cout<<"Yes\n";
}
else cout<<"No\n";
}
}

}