Statistics

Problem Statement for "Decipherability"

Problem Statement

You have a string s that contains at least K characters. Cat Snuke will remove exactly K characters from the string. Afterwards, Snuke will show you the new string and you have to guess the original indices of all removed characters. You win the game if you guess all of them correctly.

For example, suppose that s="snuke" and K=2. Snuke removed two characters and showed you the string "nue". In this situation you can easily deduce that Snuke must have removed the characters s[0] and s[3]. You announce that the indices of removed characters are 0 and 3, and you win the game.

You are given the String s and the int K. Return "Certain" (quotes for clarity) if you can always be sure to win the game, regardless of which characters Snuke removes. Otherwise, return "Uncertain". Note that the return value is case-sensitive.

Definition

Class:
Decipherability
Method:
check
Parameters:
String, int
Returns:
String
Method signature:
String check(String s, int K)
(be sure your method is public)

Constraints

  • K will be between 1 and 50, inclusive.
  • The length of s will be between K and 50, inclusive.
  • Every character in s will be a lowercase letter ('a'-'z').

Examples

  1. "snuke"

    2

    Returns: "Certain"

    This is the example from the problem statement. As all characters are unique, you can always determine the indices of the erased ones.

  2. "aba"

    1

    Returns: "Certain"

    Snuke will show you one of the strings "ba", "aa", and "ab". In the first case you can be sure that he erased the character at index 0. The second and the third string correspond to indices 1 and 2, respectively.

  3. "aba"

    2

    Returns: "Uncertain"

    If Snuke shows you the string "a", there are two possibilities: either he erased the characters at indices 0 and 1, or the characters at indices 1 and 2.

  4. "abcdabcd"

    3

    Returns: "Certain"

  5. "koukyoukoukokukikou"

    2

    Returns: "Uncertain"

  6. "wolfsothe"

    8

    Returns: "Uncertain"

  7. "a"

    1

    Returns: "Certain"

  8. "aa"

    1

    Returns: "Uncertain"

  9. "ab"

    1

    Returns: "Certain"

  10. "aa"

    2

    Returns: "Certain"

  11. "ab"

    2

    Returns: "Certain"

  12. "aba"

    1

    Returns: "Certain"

  13. "aba"

    2

    Returns: "Uncertain"

  14. "aab"

    1

    Returns: "Uncertain"

  15. "aab"

    2

    Returns: "Uncertain"

  16. "aab"

    3

    Returns: "Certain"

  17. "abab"

    1

    Returns: "Certain"

  18. "abab"

    2

    Returns: "Uncertain"

  19. "abab"

    3

    Returns: "Uncertain"

  20. "abab"

    4

    Returns: "Certain"

  21. "smjqgpkcyvzselduwyeakhkxfkisaplgt"

    12

    Returns: "Uncertain"

  22. "uiwdthpz"

    6

    Returns: "Certain"

  23. "nsqypvhqtbavuxijypvxeksbaypjgmed"

    12

    Returns: "Uncertain"

  24. "gwoxjonospvmprezgql"

    8

    Returns: "Uncertain"

  25. "ynyqpmaopqhumqwjtjyklxpd"

    2

    Returns: "Uncertain"

  26. "xlgmbh"

    4

    Returns: "Certain"

  27. "kkwknmvoaezqtszcbkjupylyayi"

    22

    Returns: "Uncertain"

  28. "ovkfrqyzpeybhwoupgcbrekwwiuccjpdxldpsdwfnwmanwxifk"

    20

    Returns: "Uncertain"

  29. "upgklvurhuaohwjxirwyptpphkgzeoxnwargcjmbr"

    25

    Returns: "Uncertain"

  30. "zhyboydtftysfojxfiihotes"

    3

    Returns: "Uncertain"

  31. "mzyejumfwmwmij"

    13

    Returns: "Uncertain"

  32. "wwhtqbebjh"

    7

    Returns: "Uncertain"

  33. "puqgyjuzasfljvxjtfezmflosrmzwjz"

    23

    Returns: "Uncertain"

  34. "dyjlvnnbxgawjkknkwgtxxkppjenmjydmoctlwvym"

    6

    Returns: "Uncertain"

  35. "athghnep"

    3

    Returns: "Uncertain"

  36. "kvolwqyzsunlheydmmyne"

    1

    Returns: "Uncertain"

  37. "emirugvifebjosoevbpnqxueoewjbewboijdxmdyacnpbytu"

    38

    Returns: "Uncertain"

  38. "xebqixjglplcsut"

    11

    Returns: "Uncertain"

  39. "zsgpzsdljtkqbftwyiynpfbkx"

    23

    Returns: "Uncertain"

  40. "afbatastyktvji"

    5

    Returns: "Uncertain"

  41. "acacbaccabcababcaaacccacaccbaababcaca"

    14

    Returns: "Uncertain"

  42. "bcccddd"

    2

    Returns: "Uncertain"

  43. "eddaee"

    5

    Returns: "Uncertain"

  44. "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"

    30

    Returns: "Uncertain"

  45. "ecbbeeecacbaadaeeacbaecdbbaacbdebcabdabaab"

    17

    Returns: "Uncertain"

  46. "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"

    32

    Returns: "Uncertain"

  47. "bbaabaabbabbaabbabbbaaaaaaabaaababbabbbbaaaaaabb"

    43

    Returns: "Uncertain"

  48. "ebcedeacceeabbabaddbbccabbeabbebebdcedc"

    1

    Returns: "Uncertain"

  49. "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"

    25

    Returns: "Uncertain"

  50. "aaaaaaa"

    2

    Returns: "Uncertain"

  51. "acbbcac"

    6

    Returns: "Uncertain"

  52. "aaaaaaaaaaaaaaaaaaaaaaaaa"

    15

    Returns: "Uncertain"

  53. "aaabacacdbdcbcdad"

    15

    Returns: "Uncertain"

  54. "ddbcebb"

    7

    Returns: "Certain"

  55. "abaaababbabaabaaabbaaaabbbba"

    7

    Returns: "Uncertain"

  56. "aaaaaaaaaaaaaaa"

    3

    Returns: "Uncertain"

  57. "bbbabababbaabbbaabbbabbaaabbbbbbabbbbaaaba"

    8

    Returns: "Uncertain"

  58. "cbbbbabcbdddccdeddebbbbceaacbaccebeb"

    8

    Returns: "Uncertain"

  59. "baabba"

    4

    Returns: "Uncertain"

  60. "abaabbaabbaabbbbaabbbaaabaababbbababaa"

    10

    Returns: "Uncertain"

  61. "ccecebceeecbecbeadcbcdcaeeddbbddbeeeaaebbabe"

    44

    Returns: "Certain"

  62. "abbbbbbababababbbbbbabaaaaaaaaba"

    32

    Returns: "Certain"

  63. "bbcaabcbccdbaadabccadaccaddbbdbdbacbcbaddcb"

    43

    Returns: "Certain"

  64. "baabbabaaaabaaabbabaaabbaababbaababbaaabaaabaa"

    46

    Returns: "Certain"

  65. "babacbbcdcadbbdbcdbadccadcddadabbacaabbcccdddbd"

    47

    Returns: "Certain"

  66. "deagcbfdeagcbfdeagcbfdeagcbfdeagcbfdeagcbf"

    6

    Returns: "Certain"

  67. "dtlgbauprksjqefmhncoidtlg"

    20

    Returns: "Certain"

  68. "abc"

    2

    Returns: "Certain"

  69. "fmedinphbacjlkog"

    14

    Returns: "Certain"

  70. "incldfjapmoqrutvhkgbeisnldcjafmpoqurtvkhbg"

    20

    Returns: "Certain"

  71. "kvqjdcsfhbwtuirmgopnleakjvqdschbfwiumrgotlna"

    20

    Returns: "Certain"

  72. "bahcgidefbahcgidefbahcgidefbahcgidefbahc"

    8

    Returns: "Certain"

  73. "gjecihbdagfjechbdigajefhcbdgijafhebcdgjifaehb"

    8

    Returns: "Certain"

  74. "doabuishmvljqencrtwfpgokbauidsmhlvqejrcnwftpkbagod"

    20

    Returns: "Certain"

  75. "ifdnjmbelkcaghfdinmbjlekagcfdihn"

    12

    Returns: "Certain"

  76. "adcfeacfeadfcbe"

    3

    Returns: "Certain"

  77. "lapuvtndgrshqfomewkbilcauvptjgdrnqshfomebwiklcu"

    20

    Returns: "Certain"

  78. "abecfagebdacgbdafg"

    4

    Returns: "Certain"

  79. "ablkjhcgedfiablkjhcgedfiablkjhcgedfiabl"

    11

    Returns: "Certain"

  80. "nfmctpkjaedigqorlhsu"

    18

    Returns: "Certain"

  81. "fbegcafdbegfadbgcedbgcefbgcdaegfdbcgade"

    4

    Returns: "Certain"

  82. "kjaceibhgld"

    9

    Returns: "Certain"

  83. "hcdgbfeahcd"

    7

    Returns: "Certain"

  84. "abdc"

    4

    Returns: "Certain"

  85. "ajindgobchmlekajfidn"

    13

    Returns: "Certain"

  86. "costaqminplhfkjrdebgcostaqminplhfkjrdebgcostaqm"

    20

    Returns: "Uncertain"

  87. "aedhbfgceadhfgcbedahfc"

    7

    Returns: "Uncertain"

  88. "rmfcqosdhulibkgaetpnrjmcqosdhflibukaetgnrjmpcos"

    20

    Returns: "Uncertain"

  89. "bujengctfmohivqplrasbduengcjfktohmqivlrsbdpaune"

    20

    Returns: "Uncertain"

  90. "dbjechagdifbecajhdgbfieajdgchbfeijdcgha"

    8

    Returns: "Uncertain"

  91. "coidjkqslhpabrgnefmcoidjkqslhpabrgnefm"

    19

    Returns: "Uncertain"

  92. "fcheagdbhef"

    6

    Returns: "Uncertain"

  93. "dbclhkjaeg"

    10

    Returns: "Certain"

  94. "befcd"

    5

    Returns: "Certain"

  95. "ab"

    2

    Returns: "Certain"

  96. "bcdegfbcedfgc"

    5

    Returns: "Uncertain"

  97. "diabjtvornuseclmphfqdkibjtagovrn"

    20

    Returns: "Uncertain"

  98. "aaaaaaaaaaaaaaaaa"

    1

    Returns: "Uncertain"

  99. "bfhgdceafbghcdafbghe"

    7

    Returns: "Uncertain"

  100. "fodpciehsgarnjmlqtbufkdopiehcsganrmjqtbufkldpieh"

    20

    Returns: "Uncertain"

  101. "fbdejihgafcbedkjihfgbeadjkifcbgadehkijfgb"

    9

    Returns: "Uncertain"

  102. "cbc"

    2

    Returns: "Uncertain"

  103. "gdealchbjfidealc"

    10

    Returns: "Uncertain"

  104. "scknraogtfiemlupqbhjdcknsarogfteilupmbqhjcknds"

    20

    Returns: "Uncertain"

  105. "acsukjnmphfbdgqoleritcsakunjphmfdgqolebrtiscak"

    20

    Returns: "Uncertain"

  106. "xabcdefghijklmnopqrstuvwyzxxabcdefghijklmnop"

    20

    Returns: "Uncertain"

  107. "abcdeef"

    5

    Returns: "Uncertain"

  108. "abcdefghijklmnopqrstuvwxyabcdefghijklmnopqrstuvwxy"

    24

    Returns: "Certain"

  109. "abcdefghijklmnopqrstwabcdefghijklmnopqrstw"

    2

    Returns: "Certain"

  110. "cddcc"

    5

    Returns: "Certain"

  111. "paxycerdogqijsabhfmwtonbxczmcnrwjfeaeuprohqyogummq"

    9

    Returns: "Uncertain"

  112. "abcabcabcabcabcabcabcabc"

    5

    Returns: "Uncertain"

  113. "abcdea"

    6

    Returns: "Certain"

  114. "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvw"

    26

    Returns: "Uncertain"

  115. "abcdefa"

    4

    Returns: "Certain"

  116. "bcadeafg"

    2

    Returns: "Certain"

  117. "baac"

    1

    Returns: "Uncertain"

  118. "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstu"

    24

    Returns: "Certain"

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: