NextAndPrev | Topcoder Archive

Problem Statement

Consider a string consisting of lowercase characters and following two operations that can change it:

Next: Choose a lowercase character and replace its every occurrence with the next character. The next character of 'z' is 'a' ('a' -> 'b', 'b' -> 'c', ..., 'y' -> 'z', 'z' -> 'a').
Prev: Choose a lowercase character and replace its every occurrence with the previous character. The previous character of 'a' is 'z' ('a' -> 'z', 'b' -> 'a', ..., 'y' -> 'x', 'z' -> 'y').

You can use each operation as many times as you want, and in any order you like. You are given ints nextCost and prevCost. These represent the cost of using each Next and Prev operation, respectively. You are also given two Strings start and goal. Return the minimum cost required in order to transform start into goal using the above operations. If transforming start into goal is impossible, return -1 instead.

Definition

Class:: NextAndPrev
Method:: getMinimum
Parameters:: int, int, String, String
Returns:: int
Method signature:: int getMinimum(int nextCost, int prevCost, String start, String goal)
(be sure your method is public)

Constraints

nextCost and prevCost will each be between 1 and 1000, inclusive.
start and goal will each contain between 1 and 50 characters, inclusive.
start and goal will contain the same number of characters.
Each character in start and goal will be a lowercase character.

Examples

```
5
```
```
8
```
```
"aeaae"
```
```
"bcbbc"
```
```
Returns: 21
```
There are several optimal sequences of operations. Here is one of them: "aeaae" -(Next)-> "bebbe" -(Prev)-> "bdbbd" -(Prev)-> "bcbbc". The total cost is 5 + 8 + 8 = 21.
```
5
```
```
8
```
```
"aeaae"
```
```
"bccbc"
```
```
Returns: -1
```
It is impossible to transform "aeaae" into "bccbc".
```
1
```
```
1
```
```
"srm"
```
```
"srm"
```
```
Returns: 0
```
start and goal may be the same. The cost of an empty sequence of operations is 0.
```
1000
```
```
39
```
```
"a"
```
```
"b"
```
```
Returns: 975
```
```
123
```
```
456
```
```
"pqrs"
```
```
"abab"
```
```
Returns: -1
```
```
100
```
```
19
```
```
"topcoder"
```
```
"ssszsffs"
```
```
Returns: 676
```
```
1
```
```
1000
```
```
"csk"
```
```
"wog"
```
```
Returns: 64
```
```
7
```
```
6
```
```
"qwerty"
```
```
"jjjjjj"
```
```
Returns: 125
```
```
306
```
```
26
```
```
"me"
```
```
"ii"
```
```
Returns: 572
```

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.