Problem Statement | | Little Arthur loves palindromes. A palindrome is a word that reads the same both forwards and backwards. For example, the words "racecar", "noon", and "w" are palindromes, but the words "computer", "moon", and "oh" are not.
Arthur is given a word word and he would like to transform it into a palindrome. There are three types of operations he can perform:
- add a letter at any position in the word (possibly at the beginning or end);
- erase a letter;
- change one letter to another.
However, each operation can be performed only with certain letters. For example, Arthur could be allowed to erase 'a', add 'b', and change 'c' to 'd'; no other operation would be allowed. Furthermore, nothing in this world is for free and operations with letters is not an exception - each operation Arthur can perform has a certain cost.
The descriptions of the allowed operations and their costs are given as String[] operations. Each element of operations is in one of the following forms (all quotes for clarity):
- "add c x" where c is a letter and x is a positive integer meaning that it is allowed to add a letter c and it costs x dollars;
- "erase c x" where c is a letter and x is a positive integer meaning that it is allowed to erase letter c and it costs x dollars;
- "change c1 c2 x" where c1 and c2 are letters and x is a positive integer meaning that it is allowed to change letter c1 to c2 and it costs x dollars.
Note that "change c1 c2 x" does not allow to change letter c2 to c1.
Little Arthur would like to transform word into a palindrome spending the least amount of money. Given word and operations return the minimum number of dollars Arthur needs to create a palindrome. Return -1 if it is impossible. | | Definition | | Class: | PalindromizationDiv1 | Method: | getMinimumCost | Parameters: | String, String[] | Returns: | int | Method signature: | int getMinimumCost(String word, String[] operations) | (be sure your method is public) |
| | | | Constraints | - | word will contain between 1 and 50 characters, inclusive. | - | Each character in word will be a lowercase letter 'a'-'z'. | - | operations will contain between 0 and 50 elements, inclusive. | - | Each element of operations will be exactly in the form "add c x", "erase c x", or "change c1 c2 x" (quotes for clarity) where c, c1, c2 are single lowercase letters 'a'-'z' and x is an integer between 1 and 100000, inclusive, with no leading zeros. | - | In each operation in form "change c1 c2 x", c1 and c2 will be different. | - | All elements of operations will represent different operations, i.e., all elements of operations without the cost part ("add c", "erase c", or "change c1 c2") will be distinct. | | Examples | 0) | | | | Returns: 0 | No operations are allowed but the given word is already a palindrome. |
|
| 1) | | | "topcoder" | {"erase t 1", "erase o 1", "erase p 1", "erase c 1", "erase d 1", "erase e 1", "erase r 1"} |
| Returns: 5 | Here it is allowed to erase any letter present in word and the cost of each such operation is 1 dollar. Thus, Arthur would like to obtain the longest possible palindrome. Two possible variants to erase only 5 letters result in palindromes "opo" and "oco". |
|
| 2) | | | "topcoder" | {"erase t 10", "erase o 1", "erase p 1", "erase c 1", "erase d 1", "erase e 1", "erase r 1"} |
| Returns: 7 | The same situation as previously except erasing letter 't' now costs 10. Because of that it is no longer optimal to obtain the longest possible palindrome. |
|
| 3) | | | "caaaaaab" | {"change b a 100000", "change c a 100000", "change c d 50000", "change b e 50000", "erase d 50000", "erase e 49999"} |
| Returns: 199999 | One way to palindromize "caaaaaab" is to change letters 'c' and 'b' to 'a's right away obtaining "aaaaaaaa". This would cost 200000.
However, a slightly cheaper way is to perform the following sequence of operations:
- "caaaaaab" - change 'c' to 'd' (costs 50000)
- "daaaaaab" - change 'b' to 'e' (costs 50000)
- "daaaaaae" - erase 'd' (costs 50000)
- "aaaaaae" - erase 'e' (costs 49999)
- "aaaaaa"
This palindromization will cost 199999 in total. |
|
| 4) | | | "moon" | {"erase o 5", "add u 7", "change d p 3", "change m s 12", "change n d 6", "change s l 1"} |
| Returns: -1 | Many words can be constructed here (e.g., "moon", "mood", "mud", "soon", "sun", "loop"), however, no palindrome is obtainable. |
|
|
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
|