Statistics

Problem Statement for "EllysTwinLetters"

Problem Statement

We say that a letter in a string has a twin if it has the same letter immediately to its left or immediately to its right (or both).

For example, in the string "AARDVARK" each of the first two 'A' has a twin (but the third 'A' does not) and in the string "FLUSSSAND" each of the three 'S' has a twin.


Elly has a String S containing at least two characters.

The girl can alter her string as many times as she likes. In each operation she chooses one valid index i and either increments or decrements the letter S[i].

Incrementing a letter changes it to the next letter in the alphabet (e.g., 'A' to 'B', 'L' to 'M', and 'Y' to 'Z'). Decrementing a letter changes it to the previous letter in the alphabet (e.g., 'B' to 'A', 'M' to 'L', and 'Z' to 'Y'). The letter 'A' cannot be decremented and the letter 'Z' cannot be incremented.

Multiple operations may be applied to the same index. Thus, S can be transformed into any other string of the same length.


Elly wants to alter her S into a string in which each letter has a twin. Please find and return the minimal number of operations needed.

Definition

Class:
EllysTwinLetters
Method:
getMin
Parameters:
String
Returns:
int
Method signature:
int getMin(String S)
(be sure your method is public)

Constraints

  • S will contain between 2 and 100 characters, inclusive.
  • Each character of S will be an uppercase letter of the English alphabet ({'A'-'Z'}).

Examples

  1. "TOPCODER"

    Returns: 30

    Some of the strings we can produce from the string "TOPCODER" are: "TTPPOOEE" in 0 + 5 + 0 + 13 + 0 + 11 + 0 + 13 = 42 operations; "PPPEEEEE" in 4 + 1 + 0 + 2 + 10 + 1 + 0 + 13 = 31 operations; "OOOOOOOO" in 5 + 0 + 1 + 12 + 0 + 11 + 10 + 3 = 42 operations; "SSEEEKKK" in 1 + 4 + 11 + 2 + 10 + 7 + 6 + 7 = 48 operations; "PPPDDDLL" in 4 + 1 + 0 + 1 + 11 + 0 + 7 + 6 = 30 operations; "GGLLHHFF" in 13 + 8 + 4 + 9 + 7 + 4 + 1 + 12 = 58 operations. Out of the options above, the transformation into "PPPDDDLL" is the one with the fewest operations: 30. As it turns out, this answer is optimal: there is no solution with fewer operations for the string "TOPCODER". (There are other optimal solutions that also require exactly 30 operations but produce a different string.)

  2. "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

    Returns: 13

    Each letter on an even position (counting from zero) can be incremented, achieving "BBDDFFHHJJLLNNPPRRTTVVXXZZ". We have incremented once 13 letters, thus the number of operations we have used is 13. This is the minimal number of operations for this test.

  3. "ESPRIT"

    Returns: 25

  4. "WITHOUTITIMJUSTESPR"

    Returns: 54

  5. "NOZAPHODJUSTVERYVERYIMPROBABLE"

    Returns: 93

  6. "FROMALLTHETHINGSIVELOSTMYMINDIMISSTHEMOST"

    Returns: 111

  7. "ABRACADABRA"

    Returns: 38

  8. "FAILEDSYSTEMTEST"

    Returns: 40

  9. "HEYTHEREWHOEVERISREADINGTHETEXTINTHETESTS"

    Returns: 134

  10. "ONADARKDESERTHIGHWAYCOOLWINDINMYHAIR"

    Returns: 115

  11. "WELCOMETOTHEHOTELCALIFORNIASUCHALOVELYPLACE"

    Returns: 120

  12. "WEREJUSTTWOLOSTSOULSSWIMMINGINAFISHBOWL"

    Returns: 93

  13. "NOWIMLAYINGDOWNTOSLEEPPRAYTHELORDMYSOULTOTAKEIFIDI"

    Returns: 142

  14. "HUSHLITTLEBABYDONTSAYAWORDANDNEVERMINDTHENOISEYOUH"

    Returns: 176

  15. "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"

    Returns: 0

  16. "ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ"

    Returns: 0

  17. "AZAZAZAZAZAZAZAZAZAZAZAZAZAZAZAZAZAZAZAZAZAZAZAZAZAZAZAZAZAZAZAZAZAZAZAZAZAZAZAZAZAZAZAZAZAZAZAZAZAZ"

    Returns: 850

  18. "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAMZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ"

    Returns: 12

  19. "AMAMAMAMAMAMAMAMAMAMAMAMAMAMAMAMAMAMAMAMAMAMAMAMAMAMAMAMAMAMAMAMAMAMAMAMAMAMAMAMAMAMAMAMAMAMAMAMAMAM"

    Returns: 408

  20. "ANANANANANANANANANANANANANANANANANANANANANANANANANANANANANANANANANANANANANANANANANANANANANANANANANAN"

    Returns: 442

  21. "AMANAMANAMANAMANAMANAMANAMANAMANAMANAMANAMANAMANAMAMANAMANAMANAMANAMANAMANAMANAMANAMANAMANAMANAMANAM"

    Returns: 432

  22. "AOAOAOAOAOAOAOAOAOAOAOAOAOAOAOAOAOAOAOAOAOAOAOAOAOAOAOAOAOAOAOAOAOAOAOAOAOAOAOAOAOAOAOAOAOAOAOAOAOAO"

    Returns: 476

  23. "ABCGHIMNOSTUYZA"

    Returns: 33

  24. "ABCEFGIJKMNOQRSUVWYZA"

    Returns: 37

  25. "AA"

    Returns: 0

  26. "AZ"

    Returns: 25

  27. "XY"

    Returns: 1

  28. "IM"

    Returns: 4

  29. "OK"

    Returns: 4

  30. "OOK"

    Returns: 4

  31. "AXA"

    Returns: 23

  32. "ABZ"

    Returns: 25

  33. "BQESLACSHECSYNWBBHQZOZVVRVZFXOKFVFYNUKOISPTBVVCNFSXYRMPRGMWCIGQEJVYFHBHQVORLHGZQTSLGCZQTNVTLTNT"

    Returns: 285

  34. "VJOEZPTVPLPBIZWXPARCJDMFELKQJJSXVLYQOCOCEAMHIDZFWGIKNIQIOUJMRUNQGFTBGTWGLLKYXXDE"

    Returns: 208

  35. "UKAAFWWCROEZEMOACBBXIMGRGMPIDJHCESSQYSDIPWWWLHJVWHOGLBZJVFVDSTDERMAPQSYKDOPYGCUVDMOVSUG"

    Returns: 245

  36. "TBQOFRXFEJIJCPJDBKXQIGSVWCEPTTTUSVKOCTLMFVBDXUDUCHCEOPDYJNDNYONZWGDQXHMKXZWZSRWIELFM"

    Returns: 224

  37. "YAJLQZXICTMUBCOTLCMPRXFQNBORKJRDCQHSUCKMWPLELTBXAJLKMHFTFVDGNRKEOCJRNBZNGPUULQDGLITRJ"

    Returns: 272

  38. "RUQODSDBUMDCHDJVFSWFJEIPWLYHGBUAHATIPEZCVMPNPATCBMPWWLQYJKCIJMNKEQVACJUNVIZUXFENZRFBK"

    Returns: 260

  39. "AHOUPJLQBAQARPQSHOJYPCFWTFOMDYHWZTNVJTYQQPDVFGYJUETAZIVJTVOFXVWJQDCMRADJZQGLZALFXWCOZPBCXDL"

    Returns: 314

  40. "YKZOYZROVWZYJUCQNYYNPUMVDNHVEZIIOTMCDIYREQAZHXAGDAATBUGWPPBVYBXTBDWSHEPTKGJLZWTRVGRNCTHMVAM"

    Returns: 302

  41. "ZFZEFUHFLEZFNPAVSCWYCIREKIHTOFGIHONNSUVGWKTBMDZBJLEWYFZSHKASLVSWAKHJUKLTUWMRDNKGFLMR"

    Returns: 283

  42. "IROAIASCAHSONDHGBISSMLHSKYZYCHLWRHAFAJGEOVOLIENESLCWGKJPAPUDIMUAWUVYRUVPPWCDITYHHWHADJAEYDCXFGI"

    Returns: 287

  43. "PCWOUEVNHTQEIPRUULXOOVYCMFVVHHLNEMCQWOYFVIEBAITCZSDZRMTKWSQXZWMZWXYWTIJMASJGQIWDXWJQCGNNXNZTRTJYXFD"

    Returns: 289

  44. "VVFFRZXOQRZMPKAKKSFIXVWANUGXXEXYGWFPRPTEWUOXWLUPPKIQKBEKLUOYQGDUAWGYZCJJUUQYJEGK"

    Returns: 233

  45. "SWZNIYUZGPKSSKTDQYZTJDKDGHNBVDEKZTWDPKHTEMKHKOSGEWLTYAGRBLJJRPVBAOOQVHKXGFMFZOXQG"

    Returns: 231

  46. "EHRLYNQPXLSPNMHWHCOBQWQYQSNCGJDXRNTVAYFKWIRJCPWIGEXFDULUVOQIFLJRCHHGMWVMOGRGVXMOFKCHHEPEOUVKQQHD"

    Returns: 268

  47. "BLQHJDMBDKPAMQAKLUCVMPDXWWMPAIYHXKKIKDTBLSGMDIDBEAALMFSNDUZXOJKTSMVXLJTWHCEXMQUABALNQNVZWTJHIDCWM"

    Returns: 251

  48. "CIDGXJYNLZHCZERBUZZJSJMRESXPCCFKFFVXKXKFEXIQZVFXIBGQHESMARFZHUCPPNSXZZYKOSCYEMVDWCFECMRZLFF"

    Returns: 326

  49. "RCQBLCEWJPLTFGXCICFZDWEQUWKNJZDGWPKDLRYZLLMWZMECAUKAEWCBRUFHYGGBXKGSNVXBUCWIFNCITIXAUMCUCEZNPJJ"

    Returns: 360

  50. "UVCZZWMQPIDRXWYJUWSHJOLOWYUVBZOQGZSRZFXHDSYLTCPXEVXFEMYNLUXBZVTETOXMBCBGNGPUMDNOVWU"

    Returns: 264

  51. "XMSVZRZMAOUDYIJSWAAEITBEURMWENEVQLXYTINEIRWKZAMHRQQXZSNSIEYCVVVXQAIIZYARBPRIUBQSEJSVCUIFSBF"

    Returns: 291

  52. "CWAIJFNQLIBWKJJVJKVBTUGPMBKQCGTHBKJPXMKQNFDAOJUMAGXWUMUBJGCKEESBIPDENJJPBFQFFXUHGFCC"

    Returns: 247

  53. "DWFIMOQERAWZMDFVSYWNQRWDUUCRXUMXBVGFGDAVZFZJMNNBELOLDGBSKRGXLSYMEFXQZFNXCCVEGOTDBUNNMT"

    Returns: 272

  54. "SMSHDDICRBKCYMFKJJPMCUELCQDCVRXFDBDDUWMKNAXCYOFCNDEKQNUFHKYLBRMJMDHGJOSDMQLGUINAFVSMYR"

    Returns: 255

  55. "KUAQBJISWCNKZHQBHLDIOHAMYKGHSCYITNDVARYGWYKJRRVIFSVQEVQURWJTVYSAXUXHKFAWGUELFTKIEBWHLKWFUXUWX"

    Returns: 324

  56. "DSHXADAMYVXQWHMMJYHWLQKHULKZPVJAMHPLSQMKPVLOKGVRIZCQZSTKPPFKCVBWSEFWONOGERNRNTDBMURYIXGGQMEZPDWPUQ"

    Returns: 305

  57. "AJTQXKNLQPGHYQHBCZRUAPYGERRANAHKSDEDJMWZSGSQWHVQOUVEZDJQDIVCDKTASQIBTAFUYXQOHSGOSLHPS"

    Returns: 253

  58. "BAGIWTRRYXRISBPZNGFRABOYOFVMVHAEBKHJLPWGWYLTOLBPGSMNEUIMCMNLOYZRAGEUVIAAAJBZMILO"

    Returns: 226

  59. "BZDVGKJWJRSLACQOHAPDPFKKBXWPURAPFSPJSLESTFXZJNLKPKVNQPFGTTDOVLJRKGLLAYBWLSUCAPAEPIAHEZPFZ"

    Returns: 299

  60. "LGWWIKOGGAQVVNUNJPMCCIXDLVWSARUKFHSOWMIWXPDKBQIZCURJREZFOZNZCIAWZAURBDGKGZTKFHHEZPOSDRSIVFJZEBXAB"

    Returns: 325

  61. "BPAYBJFAVQAXQHTJTHGIXZEYUGDFGTQZQBQULANNEVDPDPKXVPDFKPCEYGNKMTHDCPVIBDBXIZZQXUDOYYAXOPKKQDGTVVZZNZ"

    Returns: 335

  62. "BWMEAMZLZRFFRESCOPXZYXFZSJCGOKHMMFTKXSCWCRYBFVFMZUTVIKAFVMOUODYCWWDSFAENWHPSVLHXLVRLUWDGRL"

    Returns: 300

  63. "PVVXEHNBQPUWLPMDIANVEUKEXRRPHMBFDPDEMGDWOTNZOKBNOODHOPEGYENTOQSOERRVVCWAQENKZRFVGBHNIWYVXKBSEXV"

    Returns: 281

  64. "TSKECOZWYKDPNXSQDJOMJZDPQACPTCAMWFEQOYMKKXTZVWFDKATDQXGKYANSYBMHJZEVTQJLJDXOTHOYQTANLMWFOLIQKTMLLPDA"

    Returns: 294

  65. "BSLQPQFIPVEGKQTPQZGMDJNDJDDMGGIMPIEIIWOYRHEVRLZQNXPESUSWEOPPDISEUOJFKGOOBMUIIDKUTRTKIHLFVRPAEYDBHP"

    Returns: 261

  66. "ZOSTSRUHBGEDJIIZEXPFNAYYCIQADQIVAILGUUDKULGZVIDTQRHUYWBEFDRFTZRIIJFAJMAKNNMYQQQBAPIVZVFBLEXEBD"

    Returns: 246

  67. "FYYWQDZYVTIFGKTXZCOZXBPOZQUFHJINFKVMNCDLQWNQQYINJAIIIDBOMQXOXOJIPMYKXQBVIMGXIJFKGCMYUZNFGZRPP"

    Returns: 258

  68. "QADBRCGTKQRSQHAYBSMXPRANKJIXZDDSBDSTMXTRSJRVEINUFTHZFVVKUCIQSUBRVZSSDLGPVTPQJREAFQNJ"

    Returns: 263

  69. "ZLZNSWBAXNNFXAZSUVTBHFMPHCQXSVQSLSOQUAQZTWPJVEZMXEQRZOBNNISDTLKSDXJRRXKJCPPGIOWR"

    Returns: 266

  70. "DWRRNTLHWHEGDOLKBCFZDXCJEKKTOWSXBCLPWKLGVRBBBFSETDPMDEZZGMTXFMIEIIIRVOXVALWQFYSSAUOAYNVDCQ"

    Returns: 268

  71. "RVOJXGJEEAXRATNDVWDOWNCRPSCWEBTVOMYFEZCTFGCFROUHOZJUEUIGHXEGCHEEFJSQIJGMENXEKVHNH"

    Returns: 275

  72. "XXRVSAUHITFGBGMWHOFKIIDLNEYRZPHPTQXEERFCPRAAEBKREMELNOSURQFEQUEQGLQPIEHKBLGHXWLKMASXIUX"

    Returns: 209

  73. "GHFFXLJFAPLRUEJPRKYHSLOEBFXZCCKJARCRRKTNUFLZYWBMFXJRTEXWCLDMEWZGTDBANRZTLWXDWZWBOYHPV"

    Returns: 259

  74. "QGZKUVUUZQDPVNZAIRTSHBNUSXJYGZLQGYDWDIAYGPVKLEMYUHQCTEQQFAFQWLAULLJRZSFKICFLORRBRSQXERLEYMZWFIKBBD"

    Returns: 331

  75. "JFPLUFXQTECPKRAMMLXOQNRSKDTHXZUXMJWXXSCLTXNHMMRACWDQHEDYVZIVFVDTVBZKEFZMCYJMLJIBHHJGUDVYTQRTMMI"

    Returns: 282

  76. "FITAMPQMWYJXSCAJPRXOUWBOBDUGWHTOEDUPLUKEUTRLKXCUQCCGDMFZISOFEXUGBNIVFJTDKGNUGVUTHYPPX"

    Returns: 268

  77. "NMOJPMFQXDRTFZJYWIFVLDXFJKBAKJLEUHTALFBEOARBGEWHYEPNNUHTCFCOHJNHBFCENSVWMIREDOWAGU"

    Returns: 257

  78. "HGIUCFKVWNGWFCAIXGKJRZSCGXAGXPVHPAFYWXFPYRHBLDMGEHLREDNDURIVICOJDKKNZMTPJRUNDSWFZDBSWQLLJDGIVSFXOP"

    Returns: 300

  79. "URPIZIRQGQZKUWKIZBLTFTXMPMSJCQKWHVBTVVXNJFMNWGIQLWPRIXIWJHWXFTGIXLDDPENGRYLIPKIGKEEN"

    Returns: 278

  80. "VHJPPSUIPQCAEQNWNRNTDSUMDUONXFHOLLGEPKJDIOJBFIFRDRBSFZRZSUQRDMAIZXCIIBBHYABIFAKGMBEBLHSLFPCGPEFJULC"

    Returns: 269

  81. "DMCVRIMZSWUMOKKFZLJRIYQMZEYDSKDCGAKMXBZBLXCJRQUZWZEFEQBNVPPEDLSULAOZECXJSSLIQQVGIPCWFDTLSWX"

    Returns: 285

  82. "CNIHWXNQNOEIYAPTMRSRZNBGKVJIJIQATMPOBJXEIHRVKSEMBTEUZOUWSOGVQIVVLUDEQGBXJXLSOMWVJYDX"

    Returns: 287

  83. "GFRSYIFSMHJHTFIUFLRNDYOAIDWDJRGRYABFBARWPZGQMCIYTDEHYPNYGAXCBORTUNLUVQQKONJTEJZSUDKGY"

    Returns: 265

  84. "ZWACMCYOKJSHUWCQLESBFAHPBIGQTSHOWJGXJEPOKNILQYOIQJXPJLFSGPRSWCRHXWERHUUSEPCESXFOWYRDRUNIUODGVFMOFUPW"

    Returns: 304

  85. "VZTCGZTUYSCQIDSGXOOYWCNUNVWBUFNAUMAEFTTJXRLAQRLIYCERWDNVYITVBUFGPPBUALIFUSQDYQVHNJCUSKOPIGKJTEJTTVJ"

    Returns: 316

  86. "LIQJMOFERJBYOCGHBAPHQXEDOPJGAEWNZURKABNGOGRFFVUWUUWQDVEOPTDXMCEISJABUMKISFPHEKBQOVGDWXAULE"

    Returns: 246

  87. "DMXMAYIRGNQMKOLZHZWZFASSGXRGYSTPOGBCWHSZUMRZSFISHEYRHQNLBNWKANNJJJLJWWXLDWCJNWYAGXKQFWWKD"

    Returns: 293

  88. "LFKIKODOQGBAWDHECCKKJJUOHQKEWWXYGYJTFTQVMCHJTLXWVJJOZKLBMPSYSBXPAZQHYUWJAKISCKHTC"

    Returns: 261

  89. "NYOIXCDWNIGBHXNHLMHSQZUVRKIZNACWWTPRBQQLXJJNLJXRELAQHBYOBSVFFEERUSSSUGAXYQGAMMWSNCSU"

    Returns: 225

  90. "LFBBLBNTTXDFDFXHULGXNGLKYIXRBAUHNLFVUYGTUOQAOTMBXRRPCOPBLYVCJETARYUCSWKCJFRPJOAYGMPXTNUIIBSBOAHKI"

    Returns: 327

  91. "GHMOCMQOIQDBWIBMGBSILEKNYFMALTOHDASSDJNFSLGTYKQJUGTOPPIUZOJFPIREAIORMLTQFPEDZRHKJJRNMZKZMSS"

    Returns: 253

  92. "IHNXINOINNQYPXBPIJHBEEEYZWHFLLGYORXBHDYHWVDOIJLVTCZGRUWPAFORCDRSYYSVWLYVZTDMIFIUHWOQBWPMOEHHYVMH"

    Returns: 245

  93. "YOMURRVEEZAXPRJBWMKHRFVUMDDVUOKDLIFGBCHOAGMGQPZPWSJKUSUOXXHBVKKGOLBDADEBNCMNXALFYVI"

    Returns: 223

  94. "MLATWDRZJJNVVDSWBOFROVZWURIMNMANKGLXFYRPEVFPJGLBCPMQYJIOOHVLZDJVSWKUVGMQCJRBIHSPPFBXSHSOQEILXDPSRP"

    Returns: 296

  95. "CPDWJVPRKUUDXDFJWTZMRUYIIEHOWBBMFNGSVAWFWOWQILBIDIGYCIXZWDAHYVIATJWJKTJWFZIPQOCOSFWYHVLMECRKVCRCM"

    Returns: 318

  96. "NZMGOJWYCQTLIIPBUDZKVPESLIVSDANPHICLDUOYEYYXIDCSHRMXTHBAHKYYEFFCYOWPCZWESKJDXMKLLWU"

    Returns: 246

  97. "IGFIPWHIFBPHOUNSOOYWLXTVCCPQCJIHHCADLKRBJEFKZCPEQITFDOZKBKCURTHSQBBFWKUIIZKIKASBWQMLNBMXEO"

    Returns: 243

  98. "EEIRUYDCERACCGWZRFXCSGCINDWMCLAAMTKXBRPZZYGKXOZLHCVFGKXBIUKBAWOVOCKAQRTFAJNJWSFTUGR"

    Returns: 268

  99. "HEBJKNVFYIKVATPCQXFAEAFTLFXAERDMSGGJMHAMQNHSLXCYRJJKIJSCTZKEBQOLLSSSXYYFDOBZMTDILO"

    Returns: 257

  100. "LZBERQZTHWZTEQZZRKGMYPQQGLVUOXFPHTPPBIQACMIBXGYBBTYVWYNBMZNGNMIVKQVJZQIPKTBARKWLGROE"

    Returns: 268

  101. "PSJMQFXJPBQSPIMUPGYQPSYRHOCVBTHVPNITTYDRUPOIUMDKIZUKOCFWXNQIUSZNJCBESIWWZTATYIYR"

    Returns: 253

  102. "AABYZZ"

    Returns: 2

    Catches greedy solutions that remove groups of twins too eagerly.

  103. "MUTASATBCEBNVVSKCILIAHQIANNIUXFWPEPGYKYIICAFQNNHQEYWAOEZWJOXUDXNWVDXEEMVGKXCVDQJKLCTVOCTQHOKPFGWZGTH"

    Returns: 332

  104. "BASGHDJKSGHDSAKJHDKSAHDJKASASDSADSADDS"

    Returns: 135

  105. "ASDFASDFASDF"

    Returns: 56

  106. "EFGGEMTNCNSFBAZBVWWNAUBWXBOBONEHVDFIDLFABKZLCYHHIQJTAPNAEAYQNUTJQVUONKUZJZWGAXUNEZMOQNPHWEKJHICOYTHB"

    Returns: 315

  107. "AAZZZZ"

    Returns: 0

  108. "AAZZ"

    Returns: 0

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: