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
