DNA Sequencing

Problem Statement

DNA Sequencing Problem Description A team of data scientists is studying palindromic trends in DNA sequences. The palindrome transformation cost of a string is the smallest number of character replacements needed before the string can be rearranged into a palindrome. For example, the cost of "aabcd" is 1: replacing the final 'd' with 'c' gives "aabcc" , whose letters can be rearranged into "acbca" . Given a string dna , compute the sum of the palindrome transformation costs of all of its substrings. Two substrings that occupy different positions are counted separately even when they spell the same text. > A palindrome reads the same forwards and backwards, for example "z" , "aba" and "aaa" . Strings such as "xy" and "rank" are not palindromes. Input Format A single line containing the string dna . Output Format Print one integer: the sum of the palindrome transformation costs across all substrings. The answer can exceed the range of a 32-bit integer, so use a 64-bit type. Constraint