Problem Brief

Set Total Palindrome Transformation Cost

NEW 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.

1Example 1

Input

s = "abca"

Output

Explanation

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

Limits and guarantees your solution can rely on.

1 <= n <= 10^5
s consists of lowercase English letters

Draft autosaves locally

public int setTotalPalindromeTransformationCost(String s) {
  // write your code here
}

Input

"abca"

Output