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.
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.
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 palindrome. Otherwise print "NO" (without the quotes.)
See sample input/output and explanation for details.
Input 1 11 madamimadam 6 6 z 1 a 11 b 5 z 1 b 7 z Input Case 1: YES NO NO NO NO YES
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
Search for an hour and look at the output that said to print "Case %d:". After add it, I've got AC. Lol.
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?
Just keep the count of differences in the characters and use that
My respects, sir! Great question :D AC after 9 months
No idea why m i gtn tle .
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:
use scanf, printf.Last edit: 2016-06-15 23:45:52
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:
thelazycoder: Your code should get a TLE not WA ... its been fixed ...
No idea why i am getting WA . Can you check Submission id 16171756 please ?Last edit: 2016-01-29 12:59:20