Problem: Let us define the cost of string s to be the number of characters to be replaced such that the resulting string is rearrangeable to palindrome.
For e.g., let s="abc", the cost is 1 since we can change b to a (or b to c), and the resulting string will be rearrangeable to a palindrome.
You are given a string s (1<=length<=1e5). Find the sum of the cost of all the substrings.
Please help me out with this problem.
For a palindrome string with even length, the number of occurrences of each character must be even. For a palindrome with odd length, the number of occurrences of each character must be even, except the character in the middle is odd. So you can maintain a frequency array to solve this problem.
sorry I misunderstand the problem. It says find total cost for all substrings
Someone else asked this problem, seemed a bit strange. Anyway, the problem is pretty simple (or should I say mechanical):