How should I practice Total Palindrome Substring Cost?

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

Is Total Palindrome Substring Cost associated with Uber?

FastPrep tags this as a Uber coding interview or online assessment practice problem when the problem catalog has that company context.

Problem

Total Palindrome Substring Cost

Learn this problem

UberFULLTIMEOA

See Uber 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 so that the string can be rearranged to form a palindrome. For example, the palindrome transformation cost of "aabcd" is 1, since changing 'd' to 'c' makes "aabcc", which can be rearranged to "acbca".

Given a string dna, find the total sum of palindrome transformation costs of all substrings of dna.

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

Function

totalPalindromeSubstringCost(dna: String) → long

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

totalPalindromeSubstringCost has the following parameter:

dna: a string

Examples

Example 1

dna = "abca"return = 6

For dna = "abca", the single-character substrings "a", "b", "c", and "a" each have cost 0.

"ab" has cost 1; change 'b' to 'a' to make "aa".
"abc" has cost 1; change 'b' to 'c', then it can be rearranged to "cac".
"abca" has cost 1; change 'b' to 'c' to make "acca".
"bc" has cost 1; change one character to match the other.
"bca" has cost 1; change 'c' to 'a', then it can be rearranged to "aba".
"ca" has cost 1; change 'c' to 'a' to make "aa".

Therefore the total is 1 + 1 + 1 + 1 + 1 + 1 = 6.

Example 2

dna = "acbaed"return = 19

For dna = "acbaed", the single-character substrings "a", "c", "b", "a", "e", and "d" each have cost 0.

All substrings of length 2, namely "ac", "cb", "ba", "ae", and "ed", have cost 1.
"acb", "cba", "bae", and "aed" have cost 1; one character can be changed so the substring can be rearranged into a palindrome.
"acba" has cost 1; for example, change 'b' to 'c' to make "acca".
"acbae" has cost 1; change 'c' to 'e', then it can be rearranged to "aebea".
"acbaed" has cost 2; change 'c' to 'e' and 'b' to 'd', then it can be rearranged to "aeddea". Similarly, "cbae", "baed", and "cbaed" each have cost 2.

Therefore the answer is 5 * 1 + 4 * 1 + 1 + 1 + 4 * 2 = 19.

Example 3

dna = "wwwww"return = 0

All substrings of "wwwww" are already palindrome-like because every character is the same, so every substring has cost 0. The total sum is 0.

Constraints

1 <= |dna| <= 2 * 10^5
The string dna contains lowercase English letters only.