How should I practice DNA Sequencing?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Google online assessment problems in FastPrep.

Is DNA Sequencing associated with Google?

FastPrep tags this as a Google online assessment coding practice problem when the problem catalog has that company and stage context.

Problem · String

DNA Sequencing

Learn this problem

● Hard

GoogleOA

See Google hiring insights

Problem statement

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

setTotalPalindromeTransformationCost(dna: String) → long

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! 🌷

Examples

Example 1

dna = "abca"return = 6

“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

dna = "wwwww"return = 0

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

Example 3

dna = "acbaed"return = 19

"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 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

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

The string dna contains lowercase english letters only