Statistics

Problem Statement for "NextOrPrev"

Problem Statement

Consider a string consisting of lowercase characters and following two operations that can change it:
  • Next: Choose a lowercase character other than 'z' and replace its every occurrence with the next character ('a' -> 'b', 'b' -> 'c', ..., 'x' -> 'y', 'y' -> 'z').
  • Prev: Choose a lowercase character other than 'a' and replace its every occurrence with the previous character ('b' -> 'a', 'c' -> 'b', ..., '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. These strings are special: no two characters in start are the same, and no two characters in goal are the same. 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:
NextOrPrev
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 26 characters, inclusive.
  • start and goal will contain the same number of characters.
  • Each character in start and goal will be a lowercase character.
  • The characters in start will be distinct.
  • The characters in goal will be distinct.

Examples

  1. 5

    8

    "ae"

    "bc"

    Returns: 21

    There are several optimal sequences of operations. Here is one of them: "ae" -(Next)-> "be" -(Prev)-> "bd" -(Prev)-> "bc". The total cost is 5 + 8 + 8 = 21.

  2. 5

    8

    "ae"

    "cb"

    Returns: -1

    It is impossible to transform "ae" into "cb".

  3. 1

    1

    "srm"

    "srm"

    Returns: 0

    start and goal may be the same. The cost of an empty sequence of operations is 0.

  4. 10

    1

    "acb"

    "bdc"

    Returns: 30

  5. 10

    1

    "zyxw"

    "vuts"

    Returns: 16

  6. 1000

    1000

    "abcdefghijklmnopqrstuvwxyz"

    "abcdefghijklmnopqrstuvwxyz"

    Returns: 0

  7. 1000

    1000

    "abcdefghijklm"

    "nopqrstuvwxyz"

    Returns: 169000

  8. 1000

    1000

    "nopqrstuvwxyz"

    "abcdefghijklm"

    Returns: 169000

  9. 150

    328

    "c"

    "j"

    Returns: 1050

  10. 189

    105

    "hj"

    "fu"

    Returns: 2289

  11. 676

    594

    "zq"

    "bv"

    Returns: -1

  12. 137

    80

    "np"

    "va"

    Returns: -1

  13. 217

    14

    "pzm"

    "uya"

    Returns: 1267

  14. 607

    663

    "ogw"

    "pce"

    Returns: -1

  15. 242

    434

    "kvq"

    "lnp"

    Returns: -1

  16. 879

    940

    "hetu"

    "dcgo"

    Returns: 23500

  17. 42

    440

    "oria"

    "uwst"

    Returns: -1

  18. 417

    149

    "djvkh"

    "akysg"

    Returns: 5600

  19. 976

    588

    "ypubd"

    "tqpai"

    Returns: -1

  20. 494

    615

    "gimjhx"

    "afqkbt"

    Returns: 14155

  21. 210

    438

    "bipgzoy"

    "alsbzpt"

    Returns: 6288

  22. 586

    935

    "ilwjdpfn"

    "emxgaubs"

    Returns: 20122

  23. 359

    525

    "sueqyxthl"

    "orbntspdf"

    Returns: 19425

  24. 273

    578

    "ufagnqxeso"

    "tfbjmrxesp"

    Returns: 2794

  25. 156

    106

    "knpucjavzef"

    "qruvhpeyzln"

    Returns: 7644

  26. 582

    48

    "sadebkfnotx"

    "tbhigqnsuvx"

    Returns: -1

  27. 563

    440

    "ptrbgcnlaizo"

    "rtscedkiahul"

    Returns: 10295

  28. 126

    311

    "yovlkwpjgsna"

    "zpwnkytjisob"

    Returns: -1

  29. 920

    627

    "ikxunovswelrt"

    "ghyvknwrxbjos"

    Returns: 15593

  30. 193

    494

    "mxltredcabswv"

    "ozmsqlkhbirut"

    Returns: -1

  31. 884

    512

    "nufaseixrzbqh"

    "deifukhtxcanb"

    Returns: -1

  32. 235

    986

    "ykesljtouvbfic"

    "ypjtrouswxbmni"

    Returns: 11515

  33. 907

    213

    "tlqxpyswvfhmkb"

    "rknymzpwvbflhc"

    Returns: -1

  34. 520

    88

    "nslqpfvwmkrcgb"

    "kxgcrhznyovwep"

    Returns: -1

  35. 398

    548

    "noaixgtydurkcvq"

    "lmbhxgszetpjdun"

    Returns: 9264

  36. 768

    666

    "faugpikqnodxvbzy"

    "gbshoijrmnevudzw"

    Returns: 12702

  37. 27

    314

    "rxswhmdiyvfeoatpb"

    "qwrvhjdiztfekbsnc"

    Returns: 5105

  38. 743

    756

    "lvnbxeqpodizwshkcf"

    "kulawdpnmcgzvqfhbe"

    Returns: 18900

  39. 123

    367

    "cuqypviwjterxzbogdn"

    "ernxmsivjqgpwyblhfk"

    Returns: 10770

  40. 731

    657

    "vwmgosyetihqkrlapxfd"

    "wxniotzeukjqlrmbpyhc"

    Returns: 13815

  41. 42

    267

    "lcxpvsuhoqejimfytkgzb"

    "lbwpvruhoqdjinfyskgza"

    Returns: 1644

  42. 886

    199

    "jyvlqpwbifagxsuzkmtcn"

    "jxumqovdhfcgwrtyknsep"

    Returns: -1

  43. 279

    449

    "sfugtrekbzaxypwijlhmcn"

    "retfsqdkbzavwouhjlgmcn"

    Returns: 7184

  44. 80

    760

    "nywurdavxcfthkozbegilm"

    "nywspdatxcgqjkozbehilm"

    Returns: -1

  45. 652

    855

    "umrzwesxjotcpqgkiynfla"

    "tvqkicabjesmopwlfxhdrz"

    Returns: -1

  46. 36

    729

    "xfjkimhprtbcnudzywegsvq"

    "xfkljniprtacoudzywegsvq"

    Returns: 945

  47. 96

    626

    "zdohrxqgklvutpsmayniefw"

    "zbohrxpgjkvutqslaynicfw"

    Returns: -1

  48. 816

    305

    "pwolgbicnytfaumqzjrsvekd"

    "qxpmibjcoyugavnrzkstweld"

    Returns: 14688

  49. 177

    675

    "altzrmbidjnkhevqofwsucxp"

    "aktzrlbheinjgdwqofxsucyp"

    Returns: -1

  50. 607

    12

    "mgsdalrxqypiuvtzfocbkhnj"

    "uwxeqrpmcdslkbhayzgfjvot"

    Returns: -1

  51. 87

    958

    "kmrjqsatfudhxognypcvbeiwl"

    "kmrjqtaufvdhyognzpcwbeixl"

    Returns: 609

  52. 106

    886

    "qxmfedgojlurcwptyniakshvb"

    "qxmfedgojlvrcyptzniakshwb"

    Returns: -1

  53. 845

    299

    "pavknqfozxmydglehirtjcuwsb"

    "pavknqfozxmydglehirtjcuwsb"

    Returns: 0

  54. 899

    293

    "iqyopksawrhlxtceumdfgvnzbj"

    "iqyopksawrhlxtbeumdfgvnzcj"

    Returns: -1

  55. 696

    39

    "qfhobpxvjntureigkzalscmdwy"

    "qmhxbpuljgkoreintvazscfdwy"

    Returns: -1

  56. 12

    56

    "wvu"

    "xyz"

    Returns: -1

  57. 1

    1

    "ab"

    "ba"

    Returns: -1

  58. 10

    10

    "hm"

    "mh"

    Returns: -1

  59. 1

    2

    "abc"

    "xyz"

    Returns: 69

  60. 4

    2

    "abc"

    "abc"

    Returns: 0

  61. 1

    1

    "ab"

    "de"

    Returns: 6

  62. 1000

    1

    "aeiou"

    "bcjzv"

    Returns: -1

  63. 1

    1

    "ab"

    "ac"

    Returns: 1

  64. 999

    998

    "abcdefghijklmnopqrstuvwxyz"

    "bcdefghijklmnopqrstuvwxyza"

    Returns: -1

  65. 10

    10

    "ac"

    "eg"

    Returns: 80

  66. 5

    10

    "bc"

    "da"

    Returns: -1

  67. 5

    8

    "ab"

    "dc"

    Returns: -1

  68. 1000

    1000

    "zxcvbnmas"

    "xcvbnmasr"

    Returns: -1

  69. 1

    1

    "ah"

    "ha"

    Returns: -1

  70. 1000

    1

    "ab"

    "yz"

    Returns: 48000

  71. 1000

    1000

    "zywx"

    "vust"

    Returns: 16000

  72. 1

    1

    "ab"

    "dc"

    Returns: -1

  73. 1

    1

    "ba"

    "cd"

    Returns: -1

  74. 3

    4

    "ab"

    "dc"

    Returns: -1

  75. 2

    2

    "ac"

    "cd"

    Returns: 6

  76. 7

    15

    "ab"

    "dc"

    Returns: -1

  77. 123

    123

    "ab"

    "cf"

    Returns: 738

  78. 1

    1

    "sq"

    "qs"

    Returns: -1

  79. 10

    100

    "db"

    "ac"

    Returns: -1

  80. 5

    8

    "abc"

    "def"

    Returns: 45

  81. 10

    12

    "ac"

    "ef"

    Returns: 70

  82. 10

    5

    "ab"

    "dc"

    Returns: -1

  83. 2

    2

    "ba"

    "ca"

    Returns: 2

  84. 1

    1

    "zb"

    "ya"

    Returns: 2

  85. 1000

    1000

    "abcdefghijklz"

    "mnopqrstuvwxy"

    Returns: 145000

  86. 5

    10

    "ab"

    "zc"

    Returns: -1

  87. 2

    3

    "ab"

    "zy"

    Returns: -1

  88. 100

    250

    "cdef"

    "bacd"

    Returns: -1

  89. 1

    1

    "d"

    "e"

    Returns: 1

  90. 1

    1

    "zy"

    "wx"

    Returns: -1

  91. 5

    10

    "dc"

    "ac"

    Returns: -1

  92. 1

    999

    "b"

    "a"

    Returns: 999

  93. 1

    1

    "ac"

    "zb"

    Returns: -1

  94. 25

    15

    "ac"

    "de"

    Returns: 125

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.
This problem was used for: