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 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.
Constraints

• string will contain between 1 and 10000 characters, inclusive.
• The length of string will be even.
• Each character of the string will be either 'a' or 'b' or '/'.
• aCost will be between 1 and 100, inclusive.
• bCost will be between 1 and 100, inclusive.

Input Format
First line of input will contain the number of test cases. For each test case, there will be of three lines, the first line is the string whose palindrome is to be constructed, the second is the aCost and the third is the bCost
Examples
1
aba/bab/
4
6
Returns: 10
The only way to produce a palindrome is to replace 4th character of string with 'b' and 8th character with 'a'. The first replacement costs 4, the second costs 6, so the total cost is 4+6=10.
aaaabbbb
12
34
Returns: -1
There is no '/' character, and string is not a palindrome. We have no way to change it into a palindrome.

---

Sample Input

1
baba//aaa/ab//
72
23

Sample Output

213

---

Time Limit: 2 sec(s) for all input files combined.

Memory Limit: 256 MB

Source Limit: 1024 KB 

 

Code: 

 

 

import java.util.Scanner;

public class Palindrome
{
    public static int t;
    private static Scanner sca;
    public static int[] re;
    public static int Process(String s, int a, int b)
    {
        int cost = 0;
        int n = s.length();
        char[] str = s.toCharArray();
        for(int fi = 0 ; fi < n; fi++)
        {
            if(str[fi] == '/')
            {
                if(str[n - 1 - fi] == '/')
                    if(a < b)
                    {
                        str[fi] = str[n - 1 - fi] = 'a';
                        cost += 2 * a;
                    }
                    else
                    {
                        str[fi] = str[n - 1 - fi] = 'b';
                        cost += 2 * b;
                    }
                else
                {
                    str[fi] = str[n - 1 - fi];
                    if(str[n - 1 - fi] == 'a')
                        cost += a;
                    else
                        cost += b;
                }
            }
            else
            {
                if(str[fi] == 'a')
                    if(str[n - 1 - fi] == 'b')
                        return -1;
                    else if(str[n - 1 - fi] == '/')
                    {
                        str[n - 1 - fi] = 'a';
                        cost += a;
                    }
                if(str[fi] == 'b')
                    if(str[n - 1 - fi] == 'a')
                        return -1;
                    else if(str[n - 1 - fi] == '/')
                    {
                        str[n - 1 - fi] = 'b';
                        cost += b;
                    }
            }
        }
        return cost;
    }
    public static void main(String[] args)
    {
        sca = new Scanner(System.in);
        t = sca.nextInt();
        re = new int[t];
        for(int fi = 0; fi < t; fi++)
        {
            String s;
            int a, b;
            s = sca.next();
            //System.out.println(s);
            a = sca.nextInt();
            b = sca.nextInt();
            re[fi] = Process(s, a, b);
        }
        for(int fi = 0; fi < t; fi++)
            System.out.println(re[fi]);
    }
}
 

 

Solution 2 :

 

/*
 * uncomment this if you want to read input.
import java.io.BufferedReader;
import java.io.InputStreamReader;
*/

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;


class TestClass {
    static Map<Character, Integer> costMap = new HashMap<Character, Integer>();
    public static void main(String args[] ) throws Exception {
        /*
         * Read input from stdin and provide input before running */
       

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = br.readLine();
        int N = Integer.parseInt(line);
        int result[] = new int[N];
        int total = 0;
        String input = null;
        int aCost, bCost;
        for (int k = 0; k < N; k++) {
              input = br.readLine();
              aCost = Integer.parseInt(br.readLine());
              bCost = Integer.parseInt(br.readLine());
              costMap.put('a', aCost);
              costMap.put('b', bCost);
              total = 0;
              try {
              for ( int i = 0, j = input.length() - 1; i < input.length()/2; i++, j--) {
                       total += getCheapCostToPalindrome(input.charAt(i), input.charAt(j));
              }
              System.out.println( (total > 0 ? total : "-1") );
              } catch ( Exception e) {
                  System.out.println("-1");
              }
              total = 0;
        }
    }
   
    private static int getCheapCostToPalindrome(char literal, char mirrorLiteral) throws Exception {
        if ( literal == '/') {
             if ( mirrorLiteral != '/') // single '/'
                  return costMap.get(mirrorLiteral);
             else { // double '/'
                 if ( costMap.get('a') <= costMap.get('b') )
                      return (2 * costMap.get('a'));
                 else
                     return (2 * costMap.get('b'));
             }
        } else if ( mirrorLiteral == '/' ) {
               return costMap.get(literal);
        } else if ( literal == mirrorLiteral )
            return 0;
        else
            throw new Exception("Can Never Be A Palindrome");
    }
}