The Cheapest Palindrome

Palindrome is a string that reads the same backward as forward, e.g., madam.

You are given a string whose length is even, and each character of the string is either 'a', 'b' or '/' Your task is to replace each occurrence of '/' in a string with either 'a' or 'b' such that the string becomes a palindrome.

You are also given two integers, aCost and bCost. Replacing '/' with 'a' costs aCost, and replacing '/' with 'b' costs bCost.

Return the minimum cost of replacing '/' by 'a' and 'b' such that the string turns into a palindrome. If it is impossible to obtain a palindrome, return -1.

Example:

Input:  s = "baba//aaa/ab//", a = 72, b = 23
Output: 213

Approach

C++

#include <bits/stdc++.h>
using namespace std;

void theCheapestPalindrome(string s, int a, int b)
{
    int min1 = min(a, b);
    int res = 0;
    int i = 0, j = s.size() - 1;
    int flag = 0;
    while (i < j)
    {
        if (s[i] == '/' && s[j] == '/')
        {
            res += 2 * min1;
        }
        else if (s[i] != '/' && s[j] != '/')
        {
            if (s[i] != s[j])
            {
                flag = 1;
                break;
            }
        }
        else if (s[i] == '/')
        {
            if (s[j] == 'a')
                res += a;
            else
                res += b;
        }
        else if (s[j] == '/')
        {
            if (s[i] == 'a')
                res += a;
            else
                res += b;
        }
        i++;
        j--;
    }
    if (flag == 0)
        cout << res << "\n";
    else
        cout << -1 << "\n";
}
int main()
{

    string s = "baba//aaa/ab//";

    int a = 72, b = 23;

    theCheapestPalindrome(s, a, b);

    return 0;
}