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