← 返回 uber 的题目列表Total Cost to Convert All Substrings into Palindromes
类型：online_judge
Problem: Total Cost to Convert All Substrings into Palindromes
Given a lowercase string s, for every substring s[l..r] (0 <= l <= r < n), define cost(l, r) as the minimum number of single-character replacements needed to make s[l..r] a palindrome.
A single operation replaces one character within the substring with any other lowercase letter.
Compute:
[ \text{answer} = \sum_{0 \le l \le r < n} cost(l, r) ]
Input
One line: string s
Output
One integer: the total cost.
Constraints
1 <= n <= 2 * 10^5
Example
Input:
abc
Output:
3
Example
Input
a
Output
0