@ssjgz What a solution! Just blew my mind! I wouldn’t have come up with that even if I were given a week to think. I wonder if there’s any other method of solving this without using xor hacks. Or is it maybe a standard problem to be solved using the properties of xor alone? Thank you! 
1 Like
The key to it is to realise (I actually just “knew” this from previous problems) that a) two strings are anagrams if and only if their “letter histograms” are equal and b) a string is a palindrome if and only if it’s letter histogram is either all even numbers or just one odd number i.e. we only care about letter parity.
If we think of parity of a letter, it’s a small step to thinking about representing a substring’s parity as a binary number. Then I just went through a mental checklist of known techniques, one of the first of which (by sheer good luck!) was the Olde “Prefix Sum” Trick - how can we represent (and easily update) the “letter-parity-histogram” binary number of a prefix of a string? Appending a letter will toggle the parity of that letter in the letter-parity-histogram, and “toggle” usually implies either “not” or “xor”. Thinking about xor’s and prefix xor sums made me think of the recent Guddu and his Mother, and the rest soon fell into place 
So it was mainly a case of following your nose and thinking about how to adapt well-known techniques to work with what you’ve found - plus a hefty dollop of luck
I’m betting you would have thought of it within a week
7 Likes
@ssjgz Very well explained! Yea, to be honest, I did get some Guddu and his Mother feels while going through this. Haha! Thanks for the betting on me. Cheers! 
1 Like
Awesome ! The thought process that leads to a solution is lot valuable. Btw if u don’t mind may i ask if this your first codechef handle? How much years of experience you have in sport programming? 
2 Likes
Thanks! Yes, it’s my first codechef handle - I migrated from Hackerrank as they’ve pretty much stopped doing contests.
My first actual contest was in November 2017, but I’d solved many, many practice problems by then
3 Likes
It’s great ! I’ve been reading all your posts lately ! Keep them coming, learned something new today Thanks!
3 Likes
Very much appreciate the kind words - many thanks indeed 
3 Likes
Really an amazing use of xor. @karangreat and @l_returns excited to see your approaches also.
1 Like
Depending on whether you use a std::map or a vector for numPrefixesWithXorSum, the complexity is either:
a) O(N \times |\Sigma| \times \log_2 N) time and O(N) space; or
b) O(N \times |\Sigma|) time and O(N + 2^{|\Sigma|}) space
1 Like
just tell me a simple thing ( don’t mind i m not so good coder so ) can we did in O(26*N) only
and the approach u told is very nice but can we do it in simpler more understable way for new beginners or those who don’t know about these xor properties
You can do it in O(N \times |\Sigma|) time if you don’t mind using O(N + 2^{|\Sigma|}) space for your lookup array/ vector (where |\Sigma| is the size of our alphabet i.e. 26 in this case).
I personally don’t know whether there is a simpler way of doing it.
You can do it in O(N×∣Σ∣)O(N \times |\Sigma|)O(N×∣Σ∣) time if you don’t mind using O(N+2∣Σ∣)O(N + 2^{|\Sigma|})O(N+2∣Σ∣) space for your lookup array/ vector
how??
I’ve not tried it myself, but see the comment in the code: change numPrefixesWithXorSum to be a std::vector instead of a std::map and resize it to the appropriate size (2^{26}). Should work, I think.
I just found a solution that uses the exact same strategy as yours. Here’s the link. I’m starting to think that mighty xor is the only way of accomplishing our task.
1 Like
Yeah, I really can’t think of any other way of doing it. Good find
1 Like
correct me if i m wrong just store all distinct substring in a set and check for each string in a set whether they form palindrome or not…
complexity : O(n^2 * 26)
Ok i will try it , bcz first i have to understand your above aproach ( actually still i m confused so ) but definately i will try…
and we extend this by changing sunstring to subsequences okay , but tomorrow , first i understand your approach then above distinct substring and then subsequences
1 Like