Statistics

Problem Statement for "DecodeDigits"

Problem Statement

A simple way to encode a word into a string of digits is to replace each letter by its order in the alphabet. That is, "a" will change to "1", "b" to "2", ..., and "z" to "26". For example, encode("cow")="31523" and encode("cat")="3120".

Sadly, this encoding cannot always be uniquely decoded, because two different words can yield the same string of digits when encoded. For example, encode("beard")=encode("yard")="251184".

String A is a subsequence of string B if it is possible to erase some letters of B (possibly none, possibly all of them) to obtain A. For example, "cage" is a subsequence of "cabbages".

You are given a String D containing a string of digits. If there is no string Y such that encode(Y)=D, return the String "NONE". Otherwise, find and return the longest string X with the following property: whenever encode(Y)=D, X is a subsequence of Y. If there are multiple such strings, return the lexicographically smallest one.

Definition

Class:
DecodeDigits
Method:
solve
Parameters:
String
Returns:
String
Method signature:
String solve(String D)
(be sure your method is public)

Constraints

  • D will contain between 1 and 50 characters, inclusive.
  • Each character in D will be a digit ('0'-'9').

Examples

  1. "38956"

    Returns: "chief"

    There is only one way to decode this string of digits.

  2. "13919156"

    Returns: "if"

    This string of digits can be decoded in 8 different ways. Each of them contains an "i" followed by an "f".

  3. "1122"

    Returns: ""

    We have encode("kbb")=encode("aav")="1122". The strings "kbb" and "aav" have no common subsequence other than the empty one.

  4. "3120"

    Returns: "cat"

    The only valid decoding of this string is "cat".

  5. "0"

    Returns: "NONE"

  6. "01"

    Returns: "NONE"

  7. "00"

    Returns: "NONE"

  8. "1"

    Returns: "a"

  9. "2"

    Returns: "b"

  10. "9"

    Returns: "i"

  11. "9308"

    Returns: "NONE"

  12. "111"

    Returns: "a"

    Here we have three decodings: "ak", "ka", and "aaa". They all share an "a". This will be a nasty test case. Testers: please send a message if you get it wrong on the first try.

  13. "26"

    Returns: ""

  14. "27"

    Returns: "bg"

  15. "47"

    Returns: "dg"

  16. "1211121"

    Returns: "a"

  17. "1122121"

    Returns: ""

  18. "1111121112121112111112121211111212111112121112111"

    Returns: "a"

  19. "1111121112121112111112121211111212111112122112111"

    Returns: ""

  20. "11110111201121011220121101212012210122202111021210"

    Returns: "ajatjtajatjtjbj"

  21. "200"

    Returns: "NONE"

  22. "2000"

    Returns: "NONE"

  23. "27272727272727272727272727272727272727272727272727"

    Returns: "bgbgbgbgbgbgbgbgbgbgbgbgbgbgbgbgbgbgbgbgbgbgbgbgbg"

  24. "20201020102020102010202010201020201020102020102010"

    Returns: "ttjtjttjtjttjtjttjtjttjtj"

  25. "1914614101197415173102124162551014135211514221982"

    Returns: "fjgdcjejehb"

  26. "1149319141219203111124610426102512862453751251621"

    Returns: "ictcfjdjhfecge"

  27. "2218162221191216192151226923217848512615191152610"

    Returns: "ihdhej"

  28. "2071212241131075191148652021523357106203211613716"

    Returns: "tgjgehfetcegjftcg"

  29. "15626261718161721622142131712141512189212115121223"

    Returns: "fi"

  30. "71648118314161322172321433221721173152424161612924"

    Returns: "gdhcccci"

  31. "2124971220220141012011192321210178131202161651321"

    Returns: "igtbtjatbjhate"

  32. "22119231311221021710161121610212514121712121698215"

    Returns: "jjjih"

  33. "1115102191925231181854418231919174162517131010238"

    Returns: "jedddjjh"

  34. "2113719112517205168256325192452246115188222181118"

    Returns: "gtehfcefh"

  35. "2372124112110242015172021620158159510211851125109"

    Returns: "gjttthiejeji"

  36. "3181911199914202523192162231318151213257213192425"

    Returns: "ciitg"

  37. "18241619320121818113213119517723201189112614731311"

    Returns: "ctegtigc"

  38. "20151713255182122261211131623736241315916105131612"

    Returns: "tegcfije"

  39. "5262026252672217315122820138161452264421725141418"

    Returns: "etgchthedd"

  40. "1107127151692164253131722251723196131711414123107"

    Returns: "ajggidcfjg"

  41. "49385216151266226414931314161226324817313112418826"

    Returns: "dichefdicchch"

  42. "3181911511324154161020814111225253262514813105196"

    Returns: "cdjthchjef"

  43. "56102422522212418142023111122620261124137142218124"

    Returns: "efjttg"

  44. "5321101011217221211411191972441319112229206171752"

    Returns: "ecjjgditfeb"

  45. "2622171113620571420211171616231911222262321610210"

    Returns: "ftegtjbj"

  46. "8923212515115111898112481018926142398202610182322"

    Returns: "hiihhjiihtj"

  47. "26172525221882126921231126261051423131612120192510"

    Returns: "hijeatj"

  48. "18232531011205121510316823225191324141313111511317"

    Returns: "cjtejch"

  49. "4319822321111715241948211817203125152273247111320"

    Returns: "dchdhtcgcgt"

  50. "28417"

    Returns: "bhd"

  51. "6018"

    Returns: "NONE"

  52. "52769302453669486597932"

    Returns: "NONE"

  53. "8745991281074734077413013606958722248597526159"

    Returns: "NONE"

  54. "322"

    Returns: "c"

  55. "24542289056"

    Returns: "NONE"

  56. "16319954450780292889701728262837005450"

    Returns: "NONE"

  57. "088"

    Returns: "NONE"

  58. "953"

    Returns: "iec"

  59. "63"

    Returns: "fc"

  60. "09537"

    Returns: "NONE"

  61. "28"

    Returns: "bh"

  62. "10"

    Returns: "j"

  63. "340970417531"

    Returns: "NONE"

  64. "01"

    Returns: "NONE"

  65. "01537130022532085632004772072248515597240153639"

    Returns: "NONE"

  66. "6855656774271356241965929232937367670577027803"

    Returns: "NONE"

  67. "3655987983440914459937820160694366086468132361066"

    Returns: "NONE"

  68. "94106341683053855514843896628794220564428804352"

    Returns: "NONE"

  69. "4332506645076773495362806013763177418938812045910"

    Returns: "NONE"

  70. "5381279418387332517764590531865465151534463245"

    Returns: "NONE"

  71. "258670599631905152756805559847276115851482889732"

    Returns: "NONE"

  72. "1874987942831582991411961480352765744982522235"

    Returns: "NONE"

  73. "4595016822564298068789596361218202501398222860"

    Returns: "NONE"

  74. "40215972112022789263934781139232375747941191217197"

    Returns: "NONE"

  75. "0338632521348968459132552473902625177275653742988"

    Returns: "NONE"

  76. "49520243459610694223011499214711577190256791057"

    Returns: "NONE"

  77. "33931373920984212278969638324951683061730797639"

    Returns: "NONE"

  78. "3037893243656060319407182710672934107830663583"

    Returns: "NONE"

  79. "865018127933661948996377229065441173724377620707"

    Returns: "NONE"

  80. "21"

    Returns: ""

  81. "111211111212112221112111221211"

    Returns: ""

  82. "22122221222121122121112121112112122211111"

    Returns: ""

  83. "1112111221121221222111112211111211122"

    Returns: ""

  84. "211212"

    Returns: ""

  85. "22222211111111121121121"

    Returns: ""

  86. "2222221221122222212221222121212222112112112121112"

    Returns: ""

  87. "12111222112"

    Returns: ""

  88. "222121222"

    Returns: "b"

  89. "1112"

    Returns: ""

  90. "2222221212122221222112212211111"

    Returns: ""

  91. "22121221211221"

    Returns: ""

  92. "21"

    Returns: ""

  93. "21211122111"

    Returns: ""

  94. "2211121122121121112121122121121"

    Returns: ""

  95. "7772222722"

    Returns: "gggg"

  96. "727722772222"

    Returns: "gbgggg"

  97. "7777722772"

    Returns: "gggggggb"

  98. "22772777277222272777722722727772772777227227"

    Returns: "ggbgggbgggbggggggbgggbggbggggg"

  99. "77"

    Returns: "gg"

  100. "27"

    Returns: "bg"

  101. "2722222227277"

    Returns: "bgbgbgg"

  102. "222277722"

    Returns: "ggg"

  103. "77"

    Returns: "gg"

  104. "727722722772227777722272727"

    Returns: "gbgggggbgggggbgbgbg"

  105. "11121212111111111211121222212211122221122"

    Returns: ""

  106. "21"

    Returns: ""

  107. "12"

    Returns: ""

  108. "12122212221122121211111"

    Returns: ""

  109. "1122211211121211211121211211112221111221212222111"

    Returns: ""

  110. "122111222111111221"

    Returns: ""

  111. "211112222212221112112"

    Returns: ""

  112. "12222222112122211"

    Returns: ""

  113. "21"

    Returns: ""

  114. "1212121212121211222221221121"

    Returns: ""

  115. "22112111112122212"

    Returns: ""

  116. "12121112211221112112212121121222"

    Returns: ""

  117. "211111121111111112221211112"

    Returns: ""

  118. "11"

    Returns: ""

  119. "121"

    Returns: "a"

  120. "2111211"

    Returns: ""

  121. "111211121111121111121"

    Returns: "a"

  122. "2222212122222222212122212121222222212222212"

    Returns: "b"

  123. "111121112122121"

    Returns: ""

  124. "1121211121212221121122112211221211122"

    Returns: ""

  125. "1211211"

    Returns: ""

  126. "1112112"

    Returns: ""

  127. "22111"

    Returns: ""

  128. "111"

    Returns: "a"

  129. "11121112121112121212121"

    Returns: "a"

  130. "121122222"

    Returns: ""

  131. "221221222212221211111112212121111211211212221"

    Returns: ""

  132. "1112221212122221121222221221211"

    Returns: ""

  133. "222111122222222111221121122111122112122221112"

    Returns: ""

  134. "2222212221212"

    Returns: "b"

  135. "2122222202222220212122210121212121212171112121"

    Returns: "btbtbja"

  136. "21220112121120212102221212721222392111120212221212"

    Returns: "bttbjbgitb"

  137. "22222811121211012121211111212120122112112211121"

    Returns: "bhajat"

  138. "1212121111011211202112212101217222121281111111"

    Returns: "ajtjbha"

  139. "21222221222822281211121212111119221221211121121"

    Returns: "bhbh"

  140. "1112111121182222212222272222021222122012121"

    Returns: "bgbtbta"

  141. "2112110222822222128222620111222122221221102112121"

    Returns: "jbhbhtj"

  142. "212218121211121211120211222212121221912159121"

    Returns: "atia"

  143. "1212212212112122021222711210222712121221122"

    Returns: "tbgjbg"

  144. "212122212222210211102121222101219211211222222211"

    Returns: "bjjbj"

  145. "221812121101211110111212111111111202222222122222"

    Returns: "ajajatb"

  146. "2122221122261011172222120222712120111382128121"

    Returns: "jtbgathbha"

  147. "212221222102122222822112111212219111111111121212"

    Returns: "bjbh"

  148. "22222121122812181211182121212122012221112211"

    Returns: "hbt"

  149. "22222122212121210222222252012221122211212161012112"

    Returns: "bjtj"

  150. "12211921112222212118121821210211222011120211"

    Returns: "bjtat"

  151. "22222228111111121212111722212101113921222221222"

    Returns: "bhbjib"

  152. "212922210221201211121201221122111172221282121222"

    Returns: "bibjtatbhb"

  153. "12111117111211121112011221112220221671218212"

    Returns: "attgb"

  154. "1212110211211122212121911262011121212120222221212"

    Returns: "ajtatb"

  155. "11212121210112112122111112202122222101212111"

    Returns: "jtbja"

  156. "1112221211291212121121211122011121911120212"

    Returns: "itatb"

  157. "21112721182221222222210121201111111117112211121"

    Returns: "gbjat"

  158. "11120222811137121119222211272111212711221111211"

    Returns: "atbhggg"

  159. "21111122112202221012212211121211120112101211111"

    Returns: "tbjtja"

  160. "111221211222239121112121111110221222292122222"

    Returns: "iajib"

  161. "222101211111201212022281121249212102222292222212"

    Returns: "bjatatbhibjbib"

  162. "21212122222721121911110212811157212821120121"

    Returns: "bgajbhgbhta"

  163. "21257111211171211021222221222129222122210222"

    Returns: "gajbibjb"

  164. "111821291211237121111121212011121117111212121"

    Returns: "bigata"

  165. "77777777778888888888999999999978978978978978977899"

    Returns: "gggggggggghhhhhhhhhhiiiiiiiiiighighighighighigghii"

  166. "30"

    Returns: "NONE"

  167. "2129"

    Returns: "bi"

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: