DNA Sequencing

Problem Statement

Some data scientists are developing a tool to analyze palindromic trends in DNA sequences. The palindrome transformation cost of a string is defined as the minimum number of character changes required to rearrange it into a palindrome. For example, the palindrome transformation cost for the string "aabcd" is 1 because changing the last character 'd' to 'c' makes the string "aabcc", which can be rearranged into "acbca", a palindrome. Given a string dna , determine the total sum of palindrome transformation costs for all its substrings. Note A palindrome is a sequence that reads the same backward as forward, such as "z", "aba", and "aaa". Sequences like "xy" and "rank" are not palindromes. Example Suppose dna = "abca", substrings of dna with their costs are: "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