Problem Statement
Definition
- Class:
- MinCostPalindrome
- Method:
- getMinimum
- Parameters:
- String, int, int
- Returns:
- int
- Method signature:
- int getMinimum(String s, int oCost, int xCost)
- (be sure your method is public)
Notes
- You are not allowed to change an 'x' into an 'o' or vice versa.
Constraints
- s will contain between 2 and 20 characters, inclusive.
- The length of s will be even.
- Each character of s will be either 'o' or 'x' or '?'.
- oCost will be between 1 and 50, inclusive.
- xCost will be between 1 and 50, inclusive.
Examples
"oxo?xox?"
3
5
Returns: 8
The only way to produce a palindrome is to replace s[3] with 'x' and s[7] with 'o'. The first replacement costs 5, the second costs 3, so the total cost is 3+5=8.
"x??x"
9
4
Returns: 8
There are two ways to produce a palindrome here. The cheaper one is to change both '?'s to 'x's. This costs 4+4=8. Note that you are required to replace all '?'s.
"ooooxxxx"
12
34
Returns: -1
There is no '?' character, and s is not a palindrome. We have no way to change it into a palindrome.
"oxoxooxxxxooxoxo"
7
4
Returns: 0
There is no '?' character, and s is already a palindrome. Making no replacements does not cost anything.
"?o"
6
2
Returns: 6
"????????????????????"
50
49
Returns: 980
"o??oxxo?xoox?ox??x??"
3
10
Returns: 38
"??"
1
50
Returns: 2
"o?"
1
50
Returns: 1
"?o"
1
50
Returns: 1
"x?"
1
50
Returns: 50
"?x"
1
50
Returns: 50
"xx"
1
50
Returns: 0
"oo"
1
50
Returns: 0
"xo"
1
50
Returns: -1
"ox"
1
50
Returns: -1
"??"
50
1
Returns: 2
"o?"
50
1
Returns: 50
"?o"
50
1
Returns: 50
"x?"
50
1
Returns: 1
"?x"
50
1
Returns: 1
"xx"
50
1
Returns: 0
"oo"
50
1
Returns: 0
"xo"
50
1
Returns: -1
"ox"
50
1
Returns: -1
"????????????????????"
50
1
Returns: 20
"??????????????????"
1
50
Returns: 18
"??"
6
6
Returns: 12
"?oo?"
36
40
Returns: 72
"???xo??x"
21
4
Returns: -1
"??o?x??o????"
3
36
Returns: -1
"x???????????o???"
6
33
Returns: 111
"???????????????????o"
3
12
Returns: 57
"??????????o?"
34
1
Returns: 44
"?o??o??????o??"
23
18
Returns: 213
"???oo??????o???o"
15
26
Returns: 180
"x????xxx????"
48
34
Returns: 272
"??x??x??????x?"
16
42
Returns: 254
"?xxx?x??x???????"
50
6
Returns: 66
"??x?????????x??????x"
13
15
Returns: 227
"?????????????x?????o"
8
48
Returns: 184
"?????????x??????????"
10
32
Returns: 212
"?o?ox??xx?o?xxxxo???"
13
43
Returns: 207
"oo?o??xoo?xxxxooxxxo"
25
11
Returns: -1
"???xx?ox???x?x?ooxox"
6
2
Returns: -1
"oxoooooxoxoooxoxoxox"
19
33
Returns: -1
"xoxxxooxoxooxxxxxoxx"
1
9
Returns: -1
"oxxoxxoooxxoxoxoxxxo"
49
7
Returns: -1
"????oo??????"
27
43
Returns: 270
"ox???????????xxo"
14
31
Returns: 171
"x??ooo?oo?oo??ooo?xx"
42
49
Returns: 301
"?xxx????oxo?"
31
49
Returns: -1
"???x???xo???x???"
44
16
Returns: -1
"??x????ox??o?????xo?"
23
20
Returns: -1
"?????o?xxxxx"
23
44
Returns: 243
"x???x???xxo?xox?"
4
37
Returns: 230
"o??x?o?oox???x?x?xo?"
11
7
Returns: 90
"xxooxxxxooxx"
13
2
Returns: 0
"oooxxxooooxxxooo"
48
24
Returns: 0
"ooxxxxxooooooxxxxxoo"
34
18
Returns: 0
"xxoxoxooxooooooooooo"
25
5
Returns: -1
"?????????xo??????o??"
47
46
Returns: -1
"ox?x??o??xo?????????"
12
10
Returns: -1
"o???xo?oo??x???o????"
35
41
Returns: -1
"????????????????????"
50
50
Returns: 1000
"ox"
1
2
Returns: -1
"xox?"
3
3
Returns: -1
"oo"
1
2
Returns: 0
"xo"
1
1
Returns: -1
"o??xxx"
5
5
Returns: -1
"x?xxox"
5
4
Returns: 5
"??"
49
1
Returns: 2
"xox?"
1
1
Returns: -1
"ooooox"
1
1
Returns: -1
"x?xx"
20
30
Returns: 30
"????????"
2
20
Returns: 16
"oxxo"
2
3
Returns: 0
"oo"
10
20
Returns: 0
"??xo??"
11
10
Returns: -1
"????????"
1
1
Returns: 8
"oxox"
2
3
Returns: -1
"x??o"
2
1
Returns: -1
"ox"
1
1
Returns: -1
"ooxx"
1
2
Returns: -1
"??"
5
4
Returns: 8
"?xo?"
10
10
Returns: -1
"?oxx"
1
2
Returns: -1
"oo"
1
1
Returns: 0
"?oxo"
3
3
Returns: -1
"xoxx"
3
3
Returns: -1
"xooo"
5
7
Returns: -1
"xxxxooo?"
1
2
Returns: -1
"oxooo?"
2
3
Returns: -1
"????????"
10
5
Returns: 40