Intuit Coding Question: Sum of Palindrome Modification Costs

You are given a DNA string s (characters A, C, G, T). For every substring of s you must determine the minimum number of single-character changes needed to turn that substring into a palindrome, then return the sum of those minimum costs across all substrings.

This prompt tests string reasoning, two-pointers thinking, and counting/combinatorics. A naive approach checks every substring and compares characters from the ends to the middle — O(n^3) overall for length n (O(n^2) substrings × O(n) per check). Interviewers typically expect you to start with that brute force solution, explain its cost, then optimize.

Efficient approach (O(n^2)): observe that for any pair of positions i<j the pair contributes 1 to the cost of every substring where i and j are symmetric endpoints and s[i] != s[j]. The number of such substrings equals min(i, n-1-j) + 1. So you can sum (min(i, n-1-j)+1) over all i<j where s[i] != s[j]. Alternatively, iterate over 2n-1 centers and expand outwards counting mismatches — each expansion produces one substring and you add 1 when the end characters differ.

What you should demonstrate: correct counting logic, clear complexity analysis, edge-case handling (empty string, all-equal characters), and numeric types to avoid overflow. Be prepared to discuss memory trade-offs and how variants (weighted change costs or larger alphabets) affect your solution.