Minimum palindrome cost

A palindrome is a string that reads the same from left to right as it does from right to left.  The length of a input String s is even. Each character of s is either ‘o’, ‘x’, or ‘?’ Your task in this problem is to replace each occurrence of ‘?’ in s with either ‘o’ or ‘x’ so that s becomes a palindrome. You are also given integers oCost and xCost. Replacing ‘?’ with ‘o’ costs oCost, and replacing ‘?’ with ‘x’ costs xCost.     Return the minimum cost of replacing ‘?’s by ‘x’s and ‘o’s that turns s into a palindrome. If it is impossible to obtain a palindrome, return -1 instead.

Examples

1)i/p=”oxo?xox?”, 3, 5 Returns: 8
Steps are   s[7] = ? = > s[7] replace by ‘o’ of s[0]. s[7] = o, so cost is 3.
s[3] = ? = > s[3] replace by ‘x’ of s[4]. s[2] = x, so cost is 5. Total Cost is 8.

2)i/p=”x??x”, 9, 4 Returns: 8
Steps are  s[1] = s[2] = ? > both are replaced by minimum cost 4 is ‘x’. Total Cost is 8.

3)i/p=”ooooxxxx”,12,34 returns: -1
Steps are    No ‘?’ character, and s is not a palindrome. Total Cost is -1.

4)i/p=”oxoxooxxxxooxoxo”,7,4 Returns: 0
Steps are  No ‘?’ character, and s is already a palindrome. Total Cost is 0.

5)i/p=”?o”, 6, 2 Returns: 6
Steps are  s[0] = ? = > s[0] replace by ‘o’ of s[1]. s[0] = o, so cost is 6. Total Cost is 6.

import java.util.Arrays;
import java.util.Collections;
public class MinCostPalindrom {
    public  int getMinimum(String s, int oCost, int xCost) {
        int totalvalue  = 0;
        int slen = s.length()-1;
        for (int i=0;i<=slen/2;i++) {
            if (s.charAt(i)=='?' && s.charAt(slen-i)=='?') {
                if (oCost>xCost) totalvalue+=xCost+xCost; else totalvalue+=oCost+oCost; 
            } else if (s.charAt(i)!=s.charAt(slen-i)) {
                if (s.charAt(i)=='?') {
                    if (s.charAt(slen-i)=='o') totalvalue+=oCost; else  totalvalue+=xCost;
                } else if (s.charAt(slen-i)=='?') { 
                    if (s.charAt(i)=='o') totalvalue+=oCost; else  totalvalue+=xCost;
                } else return -1;
            }
        }
        return totalvalue;
    }

    public static void main(String[] args) {
        MinCostPalindrom mp = new MinCostPalindrom();
        System.out.println(mp.getMinimum("oxo?xox?", 3, 5));
        System.out.println(mp.getMinimum("x??x",9,4));
        System.out.println(mp.getMinimum("ooooxxxx",12,34));
        System.out.println(mp.getMinimum("oxoxooxxxxooxoxo",7,    4));
        System.out.println(mp.getMinimum("?o",6,2));
        System.out.println(mp.getMinimum("????????????????????",50,49));
        System.out.println(mp.getMinimum("o??oxxo?xoox?ox??x??",3,10));
        System.out.println(mp.getMinimum("??o?x??o????", 3, 36));
    }
}
Advertisement

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: