PROBLEM LINK:
Author: Sahil Singla
Tester: Gaurav Jaiswal
Editorialist: Gaurav Jaiswal
DIFFICULTY:
EASY
PREREQUISITES:
BASIC IMPLEMENTATION
EXPLANATION:
To solve the problem, we keep count of number of characters which is needed to
change to make the string palindrome.
If count becomes 0, then at that time the string is already palindrome.
So for each query we check whether count increases or decreases by updating the value,
and then update the value.
Now if count becomes 0,print palindrome,else print -1.
See tester code for implementation of the same.
SOLUTIONS:
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
#define eb emplace_back
#define pb push_back
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define mod 1000000007
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair < ll, ll > pll;
typedef pair < int, int > pii;
typedef vector < ll > vll;
typedef vector < int > vi;
typedef vector < pll > vp;
typedef map < ll, ll > mll;
const ll INF = INT_MAX;
const float PI = 3.1415926535897932384626433832795;
const int MOD = 1000000007;
int main()
{
//freopen(".in", "r", stdin);
//freopen(".out", "w", stdout);
int tt;
cin >> tt;
while(tt--){
int n,q;
char s[100005];
cin >> n >> s;
int i = 0, j = n-1, diff = 0;
while(i<j)
{
if(s[i] != s[j])
{
diff++;
}
i++, j--;
}
cin >> q;
while(q--){
int index;
char dig;
cin >> index >> dig;
if(s[index] == s[n-1-index] && index != n-1-index && s[index] != dig)
diff++;
else if(s[index] != s[n-1-index] && s[n-1-index] == dig)
diff--;
s[index] = dig;
if(!diff)
cout << "Palindrome\n";
else
cout << "-1\n";
}
}
return 0;
}
Tester's Solution
#include<bits/stdc++.h>
#define MOD 1000000007
#define INF 10000000000000001
#define F first
#define S second
#define LB lower_bound
#define UB upper_bound
#define vc vector
#define vll vector<long long>
#define pll pair<long long,long long>
#define pb push_back
#define all(v) v.begin(),v.end()
#define T ll test;cin>>test; while(test--)
#define rep(i,a,n) for(ll i=a;i<(long long)n;++i)
#define repr(i,n,a) for(ll i=n;i>(long long)a;--i)
#define endl '\n'
#define MAX 1000005
typedef long long ll;
typedef long double ld;
using namespace std;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
T{
ll n;
cin>>n;
string a;
cin>>a;
ll m;
cin>>m;
ll cnt=0;
rep(i,0,n/2){
if(a[i]!=a[n-i-1])++cnt;
}
while(m--){
ll x,y;
cin>>x>>y;
y+='0';
if(a[x]!=y&&y==a[n-x-1])--cnt;
if(a[x]==a[n-x-1]&&y!=a[n-x-1]&&x!=(n-x-1))++cnt;
a[x]=y;
if(cnt){
cout<<-1<<endl;
}else{
cout<<"Palindrome"<<endl;
}
}
}
return 0;
}