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! 🌷
Example 1:
Input: dna = "abca"
Output: 6
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.
Example 2:
Input: dna = "wwwww"
Output: 0
Explanation:Givendna = "wwwww", all substrings are already palindromes with cost = 0, hence the total sum is 0.
Example 3:
Input: dna = "acbaed"
Output: 19
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.
1 <= |dna| <= 2 * 10^5The string dna contains lowercase english letters only
input:
output: