Sum palindrome-change costs over all substrings

Q: Sum palindrome-change costs over all substrings

This is a Coding & Algorithms interview question from Intuit for Software Engineer roles. View the full question and solution on PracHub.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

You are given a DNA string dna consisting only of characters A, C, G, T.

For any substring dna[l..r], define its palindrome modification cost as the minimum number of single-character substitutions required to make that substring a palindrome. (Equivalently, it is the number of mismatched character pairs when comparing from both ends: count of indices i where dna[l+i] != dna[r-i] for i < (r-l+1)/2.)

Compute the sum of palindrome modification costs over all substrings of dna, and output the result as a 64-bit integer.

Input

A single string dna .

Output

A single integer: the sum of costs across all substrings.

Notes

You may assume the result fits in a signed 64-bit integer ( long / int64 ).

Sum palindrome-change costs over all substrings

Input

Output

Notes

Comments (0)