Palindrome with Replacement – Minimum Adjacent Difference

Problem

Given a string s containing lowercase English letters and the character ?.

We have to replace every ? with a lowercase English letter so that the final string becomes a palindrome.

Among all possible palindromes, we need to find the one having the minimum sum of absolute ASCII differences between adjacent characters.

If it is impossible to make the string a palindrome, return -1.

Example

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

Output:
4

One possible palindrome is:

abbbccccbbba

The adjacent differences are:

|a-b| = 1
|b-b| = 0
|b-b| = 0
|b-c| = 1
|c-c| = 0
|c-c| = 0
|c-c| = 0
|c-b| = 1
|b-b| = 0
|b-b| = 0
|b-a| = 1

Total:

1 + 0 + 0 + 1 + 0 + 0 + 0 + 1 + 0 + 0 + 1 = 4

A palindrome reads the same from left to right and right to left.

For example:

abcba

The matching positions are:

a ↔ a
b ↔ b
c ↔ c
b ↔ b
a ↔ a

For a string of length n, position i must be equal to:

n - 1 - i

Therefore, for every pair:

s[i] and s[n - 1 - i]

we have three possibilities.

Case 1: Both are fixed characters

Example:

a ... a

This is valid because both characters are already equal.

But:

a ... c

is impossible because neither character can be changed.

So we return:

-1

Case 2: One character is ?

Example:

a ... ?

The ? must become:

a

Similarly:

? ... c

must become:

c

So there is only one possible choice.

Case 3: Both characters are ?

Example:

? ... ?

Both characters must become the same character.

We have complete freedom to choose that character.

To minimize the adjacent difference, we can choose a character that continues the previous fixed character.

For example:

a ? ? c

can become:

a a a c

instead of unnecessarily introducing another character.

Therefore, the ? region does not create an additional cost between fixed characters.

Instead of constructing the entire palindrome, we can process only the left half of the string.

Why?

Consider:

a b c c b a

The adjacent differences are:

a-b
b-c
c-c
c-b
b-a

The right half contains the same differences in reverse order.

Therefore:

Total cost = 2 × cost of the left half

So we only need to find the minimum cost between consecutive characters in the left half.

Suppose the fixed characters that appear while scanning the left half are:

a → c → f

The minimum cost is:

|a-c| + |c-f|

The ? characters between them can simply be replaced with the previous character.

For example:

a ? ? c ? ? f

can become:

a a a c c c f

The cost becomes:

|a-a| + |a-a| + |a-c| + |c-c| + |c-c| + |c-f|

Only the transitions between fixed characters contribute:

|a-c| + |c-f|

Since the same transitions appear on the other side of the palindrome, multiply by 2.

We maintain a variable called previous.

It represents the previous fixed character that we encountered in the left half.

For every mirrored pair:

left  = s[i]
right = s[n - 1 - i]

we do the following:

Step 1: Check if both are fixed

If:

left != '?' && right != '?'

then they must be equal.

If:

left != right

return:

-1

Otherwise, this pair represents that character.

Step 2: If only one is fixed

If one side is ?, the other character determines what it must become.

For example:

a ?

becomes:

a a

So we use a.

Step 3: If both are ?

There is no fixed character that needs to be added.

We can continue without adding a cost.

Step 4: Calculate the difference

When we find a new fixed character:

current

and already have:

previous

the cost between them is:

Math.abs(current - previous)

Because the same transition appears on the other half:

answer += 2 * Math.abs(current - previous);

class Solution {
    public int minimumSum(String s) {

        int n = s.length();
        int answer = 0;

        char previous = 0;
        boolean hasPrevious = false;

        // Process only the left half
        for (int i = 0; i < n / 2; i++) {

            char left = s.charAt(i);
            char right = s.charAt(n - 1 - i);

            char current;

            // Both characters are fixed
            if (left != '?' && right != '?') {

                // Different characters cannot be changed
                if (left != right) {
                    return -1;
                }

                current = left;
            }

            // Left character is fixed
            else if (left != '?') {
                current = left;
            }

            // Right character is fixed
            else if (right != '?') {
                current = right;
            }

            // Both characters are '?'
            else {
                continue;
            }

            // Calculate difference from previous fixed character
            if (hasPrevious) {
                answer += 2 * Math.abs(current - previous);
            }

            previous = current;
            hasPrevious = true;
        }

        return answer;
    }
}

Let's understand the important parts of the code.

1. Store the length

int n = s.length();

We need the length to find the mirrored character.

For index i, its corresponding character is:

n - 1 - i

2. Store the answer

int answer = 0;

This stores the minimum total adjacent difference.

3. Store the previous fixed character

char previous = 0;
boolean hasPrevious = false;

previous stores the previous character that is fixed or determined.

For example:

a ? ? c ? f

while scanning, we get:

a → c → f

So:

previous = a
previous = c
previous = f

4. Process only half the string

for (int i = 0; i < n / 2; i++)

We don't need to process the complete string because the right half is the mirror image.

This also makes the solution efficient.

5. Find the mirrored characters

char left = s.charAt(i);
char right = s.charAt(n - 1 - i);

For example:

s = "abcba"

When:

i = 0

we get:

left = 'a'
right = 'a'

When:

i = 1

we get:

left = 'b'
right = 'b'

if (left != '?' && right != '?') {

Both characters are known.

For example:

a ... a

is valid.

But:

a ... c

is impossible.

Therefore:

if (left != right) {
    return -1;
}

else if (left != '?') {
    current = left;
}

If the left character is fixed, the right ? must become the same character.

For example:

a ... ?

becomes:

a ... a

Similarly:

else if (right != '?') {
    current = right;
}

handles:

? ... c

which becomes:

c ... c

else {
    continue;
}

When both characters are ?, we don't have a fixed character to process.

We can choose a suitable character later without increasing the minimum cost.

This is the most important line:

answer += 2 * Math.abs(current - previous);

Suppose:

previous = 'a'
current = 'c'

ASCII values are:

'a' = 97
'c' = 99

Therefore:

|97 - 99| = 2

The same transition appears on the other side of the palindrome.

So:

2 × 2 = 4

is added to the answer.

Consider:

s = "a???c??c????"

We process the mirrored pairs.

The important fixed characters encountered from the left half are:

a
c

The transition is:

a → c

ASCII difference:

|97 - 99| = 2

Because it appears on both sides:

2 × 2 = 4

Therefore:

answer = 4

The important point is that a sequence of ? characters between two fixed characters does not force us to create additional cost.

Suppose:

a ? ? ? c

We can choose:

a a a a c

The cost is:

|a-a| + |a-a| + |a-a| + |a-c|

which is simply:

0 + 0 + 0 + |a-c|

So there is no benefit in choosing intermediate characters such as:

a b c d c

because that would create unnecessary differences.

Thus, we only need to consider the transitions between consecutive fixed characters.

Let n be the length of the string.

Time Complexity

O(n)

We scan approximately half of the string.

Since:

n / 2 = O(n)

the overall complexity is O(n).

Auxiliary Space

O(1)

We only use a few variables:

answer
previous
hasPrevious
left
right
current

No additional array or string is required.

The main ideas used in this problem are:

1. Palindrome property

   CodeCopy

   s[i] == s[n-1-i]

2. Check mirrored characters

   • Same fixed characters → valid.

   • Different fixed characters → impossible.

   • ? + fixed → replace ? with the fixed character.

   • ? + ? → choose a suitable character.

3. Process only half of the string.

4. Ignore consecutive ? regions when calculating cost, because they can be filled with the previous character.

5. Every transition occurs twice in a palindrome, so:

   CodeCopy

   total cost = 2 × left-half cost

6. The final solution runs in:

   CodeCopy

   Time: O(n)
   Space: O(1)

Pattern to Remember

When you see a problem involving:

Palindrome + '?' + minimum cost

first think about the mirrored pairs:

i  ↔  n - 1 - i

Then think about the fixed characters and the cost between consecutive fixed characters. This reduces the problem from constructing many possible strings to a simple linear scan.