A string is called "palindrome-like" if it can be rearranged in any way to become a palindrome. eg : aabb is a palindrome as it can be rearranged like abba. For any string you are allowed to change any number of characters in it to make it "palindrome-like". Let this amount for any string be "cost" Find the total sum of palindrome transformation cost of all the substrings of the given string.
eg:
abca ->
"a", "b", "c", "a", with cost = 0
"ab", cost = 1, we can change 'b' to 'a' and it becomes "aa" which is a palindrome.
"abc", cost = 1, we can change 'b' to 'c' and it can be rearranged to "cac" which is a palindrome.
"abca", cost = 1, we can change 'b' to 'c' and it becomes "acca" which is a palindrome.
"bc", cost = 1, we can change 'b' to 'c' and it becomes "cc" which is a palindrome.
"abc", cost = 1, we can change 'b' to 'c' and it can be rearranged to "cac" which is a palindrome.
"abca", cost = 1, we can change 'b' to 'c' and it becomes "acca" which is a palindrome.
"bc", cost = 1, we can change 'b' to 'c' and it becomes "cc" which is a palindrome.
"bca", cost = 1, we can change 'c' to 'a' and it can be rearranged to "aba" which is a palindrome.
"ca", cost = 1, we can change 'c' to 'a' and it becomes "aa" which is a palindrome.
constraint: n <= 10**5
Can anyone help please?
There is common technique for such palindrome-like strings: for each string create bitmask, where 1 on i'th position represents i'th symbol occurs odd number of times, 0 otherewise. It is easy to see that string is palindrome-like if and only if there is zero or one 1 in corresponding bitmask. Let F(bitmask) be count of 1's in bitmask. Then answer is sum of max(0, F(bitmask)-1) over bitmasks for all substrings. There is also nice property of this bitmasks: we can use XOR to delete/add symbols to substrings, so in original task we can create prefix XOR: pref[i] = bitmask for substring 0...i. Then task can be reduced to following: We have array ar of integers (our prefix bitmasks). We want to count sum of max(0, F(ar[i]^ar[j])-1) over all i < j. I can give a hint for final solution: you can enumerate all bits and count their contribution to answer. But you need to perform decrement for each substring, so you should take into account all zero substrings (they have answer 0, not -1, that is reason for max() in formula above).
Can u please provide link to any source code doing the same.
I am sure answer is F(bitmask) / 2 instead
Yes, you are right. Now I don't know how to solve the problem.
I would still sum up the answer for all bits & divide it by 2. The odd number case appears iff the substring length is odd, so I think we can substract #odd substring from final answer
Can you provide some psuedo code/code please. New to this trick mentioned would love to see it in action.
Not in front of PC, sorry :(
Try to start by calculating answer for single string