Problem Brief

DNA Sequencing

Some data scientists are building a utility to analyze palindromic trends in the DNA sequencing of a string. The palindrome transformation cost of a string is defined as the minimum number of characters that need to be changed in it so that it can be rearranged to form a palindrome. For example, the palindrome transformation cost of the string "aabcd" is 1 since we can change the last character 'd' to 'c' so that the string becomes "aabcc" that can be rearranged to "acbca" which is a palindrome.

Given string dna, find the total sum of palindrome transformation cost of all the substrings of the given string.

Note: A palindrome is a sequence that reads the same backward as forward, for example, sequences "z", "aba" and "aaa" are palindromes, but sequences "xy", "rank" are not.

Function Description

Complete the function setTotalPalindromeTransformationCost in the editor below. The function returns the total sum of palindrome transformation costs across all substrings.

setTotalPalindromeTransformationCost has the following parameter:

dna: string

🌷༊·° Now sending 1009th thank you to spike! 🌷

1Example 1

Input

dna = "abca"

Output

Explanation

“a", "b", "c", "a", with cost = 0 "ab", cost = 1, we change change 'b' to 'a' and it becomes "aa" which is a palindrome. "abc", cost = 1, we change 'b' to 'c' and it can be rearranged to "cac" which is a palindrome. "abca", cost = 1, we 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 change 'c' to 'a' and it can be rearranged to "aba" which is a palindrome. "ca", cost = 1, we change 'c' to 'a' and it becomes "aa" which is a palindrome. hence the answer is 1 + 1 + 1 + 1 + 1 + 1 = 6.

2Example 2

Input

dna = "wwwww"

Output

Explanation

Given dna = "wwwww", all substrings are already palindromes with cost = 0, hence the total sum is 0.

3Example 3

Input

dna = "acbaed"

Output

Explanation

"a", "c", "b", "a", "e", "d" have cost = 0 All substrings of length 2 i.e. "ac", "cb", "ba", "ae", "ed" have cost = 1, we can change either of the character to other. "acb", "cba", "bae", "aed" have cost = 1, we can change last character to first character in each of them. "acba" has cost = 1, we can change 'b' to 'a'. "acbae" has cost = 1, we can change 'c' to 'e' and it can be rearranged to "aebea" which is a palindrome. "acbaed" has cost = 2, we can change 'c' to 'e' and 'b' to 'd', then it can be rearranged to "aeddea" which is a palindrome. Similarly, "cbae", "baed" and "cbaed" have cost = 2. Hence, the answer is 5 * 1 + 4 * 1 + 1 + 1 + 4 * 2 = 19.

Constraints

Limits and guarantees your solution can rely on.

1 <= |dna| <= 2 * 10^5

The string dna contains lowercase english letters only