Palindrome with Replacement

Problem Overview

The finished string has to read the same forwards and backwards, so position i and its mirror must end up as the same letter.

Intuition

The finished string has to read the same forwards and backwards, so position i and its mirror must end up as the same letter. If both are already letters and they differ, no replacement works. A question mark copies the letter opposite it. A pair of question marks can be any letter, and the cheapest choice is to change gradually between the fixed letters on either side. The total variation of that gradual change is exactly the absolute gap between those two letters, so the blanks themselves never need to be written down.

Algorithm

1Walk i from the left. Let the mirror index be n - 1 - i.
2While i is still left of its mirror, return -1 if both characters are letters and they differ.
3Resolve the character at i: use its own letter, otherwise the mirror letter, otherwise skip it.
4Add the absolute difference between this letter and the previous resolved letter.
5Return the sum after the last index.

Example Walkthrough

Input: s = "a???c??c????"

1. The ends must both be a, and the two c positions already match their mirrors.
2. The fixed letters in order are a, c, c, a.
3. The gaps are 2, 0, and 2. Filling each gap one letter at a time costs exactly that much.

Output: 4

Common Pitfalls

• Return -1 only when a mirrored pair holds two different letters. A letter opposite a question mark is fine.
• Question marks that mirror each other add no cost. Skipping them is the minimum, not an approximation.
• The sum uses successive fixed letters in left to right order, including letters that were copied from the opposite side.
• Building a new character array works but uses linear extra memory. Reading each pair from the original string is enough.

Palindrome with Replacement.java

Java

// Approach: A palindrome forces each pair s[i] and s[n-1-i] to share one
// letter. Two different letters in a pair make it impossible. A '?' copies
// the letter opposite it, and a pair of '?' can be filled later for free.
// The cheapest filling between two fixed letters changes by 1 at a time, so
// its cost is just the absolute gap between those letters. One left-to-right
// pass resolves each character from its pair and adds those gaps.
// Complexity: O(n) time, O(1) extra space.
class Solution {
    public int minimumSum(String s) {
        int n = s.length();
        int sum = 0;
        char prev = '?';
        for (int i = 0; i < n; i++) {
            int j = n - 1 - i;
            char here = s.charAt(i);
            char mirror = s.charAt(j);
            if (i < j && here != '?' && mirror != '?' && here != mirror)
                return -1;
            char c = here != '?' ? here : mirror;
            if (c == '?')
                continue;
            if (prev != '?')
                sum += Math.abs(c - prev);
            prev = c;
        }
        return sum;
    }
}

Was this solution helpful?