FastPrep
Problem · String

Set Total Palindrome Transformation Cost

● HardIntuitNEW GRADOA

A string is called "palindrome-like" if it can be rearranged in any way to become a palindrome. For example, aabb is palindrome-like since it can be rearranged to abba.

For any string, you are allowed to change any number of characters to make it palindrome-like. Let this minimum number of changes be the string's cost.

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

Also asked by Google: DNA Sequencing.

Examples
01 · Example 1
s = "abca"
return = 6

Substrings of "abca" with non-zero cost are:

  • "ab": cost 1
  • "abc": cost 1
  • "abca": cost 1
  • "bc": cost 1
  • "bca": cost 1
  • "ca": cost 1

Single-character substrings have cost 0, so total cost is 1 + 1 + 1 + 1 + 1 + 1 = 6.

Constraints
  • 1 <= n <= 10^5
  • s consists of lowercase English letters
More Intuit problems
drafts saved locally
public int setTotalPalindromeTransformationCost(String s) {
  // write your code here
}
s"abca"
expected6
sign in to submit