PLNDROME - Palindrome Or Not


It's English class now. So John is bored as usual. To get over his boredom he is doing a very strange thing. He writes an arbitrary string on his notebook and then keeps changing a single character of the string every time and tries to find out  if the string has become a palindrome.

As John is very smart this task is very simple for him.

But how simple is it for you ? Can you be as smart as the great John?

You'll have to write a code that solves the similar problem and hopefully as fast as John.

 

INPUT:

First line of the input will be an integer T (T<=15) denoting number of test cases.

Each test case starts with an integer N (1<=N<=100000) denoting the length of the string.

Next line will contain the string consisting of only small letters of English alphabet (a,b,c,...,x,y,z).

Then there will be another integer M (1<=M<=10000) denoting number of queries.

Each query will be in the form:  i x

where i will be an integer (1<=i<=N) and x will be a character. (a<= x<=z)

and it will mean that the i-th character of the string has been changed to x.

 

OUTPUT:

First you will have to print the test case number.

Then for each query in  the test case you will have to print "YES" if the given string has become a plaindrome. Otherwise print  "NO". (without the quotes )

See sample input/output and expalination for details.

 

Sample Input

Sample output

1

11

madamimadam

6

6 z

1 a

11 b

5 z

1 b

7 z

 

Case 1:

YES

NO

NO

NO

NO

YES

Explaination:

After the 1st query the string is: madamzmadam

which is a palindrome

 

After the 2nd query the string is: aadamzmadam

which is  NOT a palindrome

 

After the 3rd query the string is: aadamzmadab

which is  NOT a palindrome

 

After the 4th query the string is: aadazzmadab

which is  NOT a palindrome

 

After the 5th query the string is: badazzmadab

which is  NOT a palindrome

 

After the 6th query the string is: badazzzadab

which is a palindrome

 


hide comments
Nemanja Stojanovic: 2016-11-08 19:25:03

Can you take a look at submission 18134735? I just loop once through the string and it works for all examples for me and it should be fast enough?

sush_75: 2016-09-17 18:57:02

Just keep the count of differences in the characters and use that

akshayvenkat: 2016-09-16 17:31:36

My respects, sir! Great question :D AC after 9 months

nehae: 2016-09-02 22:47:31

No idea why m i gtn tle .
If possible please check Submission id 17595638 !
any piece of advice for optimising the code!?

setsuda: 2016-08-20 20:22:45

In C++, is using std::reverse too slow? 0.100s is a rather strict time limit. My submission ID is 17548321, I need help optimizing so I can deal with TLE.

Admin Deepak Baghel: 2016-06-15 23:18:56

use scanf, printf.

Last edit: 2016-06-15 23:45:52
chalarangelo: 2016-03-19 13:35:53

Is python 3 too slow for this? Anyone got any ideas as to how to optimize my code as I am getting TLE right now?

Md. Najim Ahmed: 2016-02-02 12:10:22

thelazycoder: Your code should get a TLE not WA ... its been fixed ...

thelazycoder: 2016-01-27 14:59:49

No idea why i am getting WA . Can you check Submission id 16171756 please ?

Last edit: 2016-01-29 12:59:20
Md. Najim Ahmed: 2015-12-27 09:35:54

@gomathi ganesan check overall complexity of your code.
you don't need to iterate over the entire string for each query to find out if it's a palindrome.

Last edit: 2015-12-27 09:36:26

Added by:Md. Najim Ahmed
Date:2015-12-05
Time limit:0.100s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY