PROBLEM LINK:
Author: Aniket Marlapalle
Tester: Devamanyu Hazarika
Editorialist: Saumyajit Dey
DIFFICULTY:
EASY.
PREREQUISITES:
Segment-Trees, Bitwise-XOR.
PROBLEM:
The problem asks to print if a certain substring of a given string is a palindrome or not. However there might be queries where any character of the string might be changed.
EXPLANATION:
In this question we have to find if any permutation of the characters from given range can form a palindrome.
In an even length palindrome every character should be present even number of times. And in case of odd length palindromes every character will appear even number of times except the character appearing in the middle of the string.
So we can just check the frequencies of 26 characters in the range and if there are less than or equal to 1 characters with odd frequency then print “YES” else print “NO”.
Subtask 1:
For every query you can iterate through the range to find the frequencies of all the characters and find the answer.
Subtask 2:
You can use segment tree to keep the track of frequencies. (This will get you 100 points).
ALTERNATIVE SOLUTION:
Using bitwise operations. Where number will be from 0 to 2^26 and 0th bit will represent parity of ‘a’ , 1st bit will represent parity of ‘b’ and so on.
Represent every character from ‘a’ to ‘z’ with numbers 2 to the power (0 to 25) and store them in a segment tree and for every node store XOR SUM of all the numbers in the range. If any character is present even number of times then that bit in the number will be zero and whichever character is present odd number of times that bit will be 1. Now we just have to check if no of bits equal to 1 in the given range is 1 or 0 the the answer will be “YES” otherwise it will be “NO”.
SUBTASK SOLUTIONS:
Subtask-1 solution can be found here.
Subtask-2 solution can be found here.