Statistics

Problem Statement for "Istr"

Problem Statement

Hero came up with an interesting way to calculate the value of any string. It works as follows:
  1. Find all distinct characters that appear in the string.
  2. For each of those characters, count the number of occurrences.
  3. Square each of those counts.
  4. Sum all those squares to get the value of the string.

For example, suppose Hero has the string "abacaba". This string contains 4 'a's, 2 'b's, and 1 'c'. Thus, its value is 4*4 + 2*2 + 1*1 = 21.

You are given a String s and an int k. You are allowed to remove at most k characters from s. Your goal is to produce a string with the smallest possible value. Compute and return that value.

Definition

Class:
Istr
Method:
count
Parameters:
String, int
Returns:
int
Method signature:
int count(String s, int k)
(be sure your method is public)

Constraints

  • s will contain between 1 and 50 characters, inclusive.
  • Each character in s will be a lowercase letter ('a'-'z').
  • k will be between 0 and the length of s, inclusive.

Examples

  1. "aba"

    1

    Returns: 2

    The optimal strategy is to erase one of the two 'a's. This produces a string with value 1*1 + 1*1 = 2.

  2. "abacaba"

    0

    Returns: 21

  3. "abacaba"

    1

    Returns: 14

  4. "abacaba"

    3

    Returns: 6

  5. "abc"

    3

    Returns: 0

  6. "wersrsresesrsesrawsdsw"

    11

    Returns: 23

  7. "abababoabaobooobbbobabbaaobobooa"

    26

    Returns: 12

  8. "ioaoeoqbkbhl"

    11

    Returns: 1

  9. "oohlaefleecoookjkoippolm"

    13

    Returns: 11

  10. "oarobokoi"

    4

    Returns: 5

  11. "qpmhoiampnokkq"

    2

    Returns: 18

  12. "bkkjlkiienhicedhoidjocbfgcoaajcaiojmknccoeogfnkc"

    18

    Returns: 64

  13. "corbodtoktmgqopaqrotoqeqgcc"

    20

    Returns: 7

  14. "aeefegaggcaffefogcbaeabbgcegebdfaaodgogacgeccaoaff"

    34

    Returns: 32

  15. "fioooohdabgeceh"

    0

    Returns: 31

  16. "oaaooaaaaooaoaaaoaaaoaaaaoaaaaoaaaoaaaaaoaaoaa"

    44

    Returns: 2

  17. "jjhonkmdlofooiibnmlmeomjidljfgmdabcooflgiolaofdof"

    15

    Returns: 90

  18. "caccbdbcbccooocobdoadaddboooddbaobdbobdccdcaadoca"

    14

    Returns: 245

  19. "pldcn"

    3

    Returns: 2

  20. "maoonescoqgalisojljkdookofjpelhmnhooqbodjio"

    0

    Returns: 191

  21. "gossla"

    5

    Returns: 1

  22. "occacdaadebofdaceabaoebeafodfocobb"

    27

    Returns: 7

  23. "ofojoeumeosovav"

    5

    Returns: 12

  24. "egfihiofckebebhofhogogjohieeoodco"

    27

    Returns: 6

  25. "abbobobbbbbaaabbbbbaobaaabaabbaaaaaaboo"

    16

    Returns: 187

  26. "horidknblooooreqkdgqrdlbdbf"

    19

    Returns: 8

  27. "jeonkhmoibnkojlionoijlhdcgoooollnfomomlnojigjgmebo"

    21

    Returns: 67

  28. "mrbjsorgedodhbrpngorrjigjbgpdspldinoohlgng"

    1

    Returns: 145

  29. "oabboaobaaoaaaa"

    9

    Returns: 12

  30. "aaoaaaaaaaaoaaaaaaaoaaooaaoo"

    1

    Returns: 449

  31. "oddogcooojfkjoko"

    1

    Returns: 51

  32. "kbbeoio"

    7

    Returns: 0

  33. "ov"

    1

    Returns: 1

  34. "aoadgbgoocbbfoabcoboffgbocebooooooedoabcohaghoff"

    34

    Returns: 24

  35. "hbmgopcosfjmodcjnoamemorcoloiocbldbkkecobmhnoeio"

    12

    Returns: 86

  36. "olfpogcnbqjleojqcoqmmoaoclbogfbjonhhlejooopleoncao"

    31

    Returns: 29

  37. "bobbaacaobacabocccccb"

    16

    Returns: 7

  38. "ofdaecabocffoccd"

    3

    Returns: 27

  39. "odocohldmbegoogioglgbokoghiijkfgoh"

    4

    Returns: 100

  40. "doofkcdjomobodcoldomooldokggoohonooojgllbohfi"

    33

    Returns: 12

  41. "cdgkoo"

    4

    Returns: 2

  42. "ad"

    0

    Returns: 2

  43. "abbaaoababbaaabaaoaabbaaabbbobboaboabaoobaa"

    30

    Returns: 57

  44. "oacflajhbjhaokdoiokeofoibohofaeokcio"

    1

    Returns: 151

  45. "aaaaaaaaooaaoaaaaaaaaaaaaaaaaoaaoaaaaaoo"

    38

    Returns: 2

  46. "gockhobobdfbjhifoffd"

    15

    Returns: 5

  47. "oviooebliforooqtokjjnaecijmrotwroohcuoboolofxgmfeo"

    12

    Returns: 84

  48. "adccccadacocdcoaddcbcacdodcdabcabbaodcb"

    2

    Returns: 307

  49. "ogfoldjdlafofeogecgdkeodbdebkccohekkoogohbchc"

    22

    Returns: 47

  50. "curnpqiaougmenowhoicjoomvukollpeuq"

    22

    Returns: 12

  51. "eegabghdfbadgebdhcghgchaeohccefdchacfedofbgffc"

    1

    Returns: 241

  52. "olblodnneflloaiodokocc"

    4

    Returns: 36

  53. "aecaaaccacebbcoabcbocadodbeceb"

    22

    Returns: 12

  54. "dftc"

    3

    Returns: 1

  55. "ioeoigsoecltdmjppbefsoaapoobcnplooccsgoamoiqoafd"

    46

    Returns: 2

  56. "bbdbbcabdoaaacoboobocdbcdccobaodaaoooaaaocbccc"

    35

    Returns: 25

  57. "nvorjmjbdmhojbmtrltqialgaoervoobxopavroowfi"

    4

    Returns: 99

  58. "cgdoodheacaafbaccgcbeohbebfaghdggcbefecg"

    36

    Returns: 4

  59. "bbgdmcckmdcofgociookdohfjafoajlahfggfoglojiebcioi"

    25

    Returns: 44

  60. "kolkbgodcjkaboogijaigojjaonioebmhcmnmljoaegkje"

    31

    Returns: 17

  61. "afoiohjajokfeooibjfojjdhcjdeoeodfbiajoo"

    0

    Returns: 211

  62. "oxnvfxwsjpoucnoaoocoaqwuioomjtmprpdopoowvopilso"

    13

    Returns: 68

  63. "odakkcdbdifmoleldihloioajfhjbodioofacajddggjoioo"

    15

    Returns: 85

  64. "dxltsjagbwciehqromko"

    7

    Returns: 13

  65. "soxstirjudooogogkooe"

    10

    Returns: 10

  66. "noapsleiophocoofooj"

    16

    Returns: 3

  67. "ohmqooy"

    6

    Returns: 1

  68. "oknonofqagisf"

    1

    Returns: 18

  69. "fdijjibkioojojjakodjce"

    10

    Returns: 16

  70. "ocfohchoefcfbgfocgbeo"

    13

    Returns: 10

  71. "aqoqollodmjggokecklnoomopbc"

    25

    Returns: 2

  72. "aeebjciioifobogoogiiicbadd"

    12

    Returns: 22

  73. "diopg"

    0

    Returns: 5

  74. "opjojolpdnoggneeajicmikcobonjcoojhnbonedlckhoooio"

    38

    Returns: 11

  75. "daecedbhgbodabhoooobacfefbhgchfe"

    2

    Returns: 104

  76. "qaooqououvogdpsajaoslnuobou"

    19

    Returns: 8

  77. "cnkggdnhgoeb"

    11

    Returns: 1

  78. "bofoaagdddoefbooadfodgooodobffebcgoeaae"

    36

    Returns: 3

  79. "eyonwvbtkmdayeokiobpkpymomfgcnosfqooogopfymgrdlkot"

    47

    Returns: 3

  80. "oefogejeoaofobffjcadaobdjiohcdfbcdobcfgbfcheejac"

    15

    Returns: 109

  81. "ldbdhkhmlnjjomooed"

    6

    Returns: 16

  82. "ooocdbadcadocabddoabacddaaacacdaobc"

    32

    Returns: 3

  83. "ftpcopajodywgoobscaycucvlrqpfxjtopx"

    35

    Returns: 0

  84. "bdlcignokifoooanomnocoipoepboiaacbhnojococfpmaakkj"

    19

    Returns: 69

  85. "abc"

    2

    Returns: 1

  86. "cbflabeeggogomeje"

    16

    Returns: 1

  87. "baocbbaaobacb"

    2

    Returns: 33

  88. "aaedddaaoebodadeedaecbdeadcdddd"

    5

    Returns: 146

  89. "beneooalctmo"

    0

    Returns: 20

  90. "efeooacboafodobcfdococcocfcfebefeo"

    23

    Returns: 19

  91. "begdcggdccfcooehoocgoegfocbgfdoghcghgehchoeoofaoao"

    8

    Returns: 230

  92. "lobghjgolkieodoiooicoinoceclidhjfoodk"

    21

    Returns: 22

  93. "aibedfeieaohiiia"

    13

    Returns: 3

  94. "bahoohfohgcdooeogebohgoeofooacdogogg"

    10

    Returns: 86

  95. "fibdeoohgfdoojjfaoccfooifoojobcacfogbocjhicfg"

    19

    Returns: 66

  96. "bobbboaabbaaaoaoabbooaabbb"

    15

    Returns: 41

  97. "cobaccabaabaabbbababocbocb"

    7

    Returns: 95

  98. "coofbcoccaghdaoaoeochoeaodooodeocdabifoaoeboo"

    40

    Returns: 5

  99. "bbobabobbbobbbbaaabcocabbaabcccbccobacoo"

    9

    Returns: 241

  100. "ooebloorooqnbrioodkdqroooblqgopofmplklbomooocrfdao"

    3

    Returns: 313

  101. "kkohhldaefpkoosgkoooopces"

    23

    Returns: 2

  102. "solocnsceijomomf"

    3

    Returns: 19

  103. "agogceoffgbeoodaecaccbobodbbobbgoodcoofocggdofgga"

    45

    Returns: 4

  104. "efhd"

    3

    Returns: 1

  105. "shoqamtooi"

    3

    Returns: 7

  106. "olhoologkfiommcnggfhdoeeno"

    9

    Returns: 27

  107. "nlhfhhooblsauasioooolmpovooexhtoypjoueo"

    3

    Returns: 136

  108. "cdbbabaacdbaeaeocbbbeb"

    13

    Returns: 15

  109. "uurleoooemobhfhloorponh"

    14

    Returns: 9

  110. "cgoffcedcdaeadgdfoafadagafoadofceadbgcecdcoobb"

    3

    Returns: 247

  111. "klfohghoco"

    10

    Returns: 0

  112. "diaoohbaojoedcfgacoejajcofaj"

    28

    Returns: 0

  113. "qmfkqohonagpoqjo"

    4

    Returns: 14

  114. "qqqqqnqqiqzqiqqqiqqqqzqkjpsqqjqqqy"

    20

    Returns: 26

  115. "zpzqqqqqtpxqiqxu"

    12

    Returns: 4

  116. "qiqffqqqqedquqqqfiqxqii"

    21

    Returns: 2

  117. "kqpqqqqisqqhqqqiniq"

    19

    Returns: 0

  118. "iqqqiqrqmiiqsiggqiqqqiqqsqq"

    6

    Returns: 123

  119. "qyqdqzqqqqwqqqqqitqqqqiqwqiqqqipmiqbkhqvqiq"

    21

    Returns: 64

  120. "qqxwyqixqwqzqxqqzqqyqiyxqyqqiqqqqiqqqqzwiy"

    28

    Returns: 34

  121. "qiqtqqkqikxqs"

    8

    Returns: 5

  122. "qqlniqdhdiqqiqq"

    2

    Returns: 41

  123. "qzqiqqzzqqqqzqqqyqiyzqiz"

    3

    Returns: 149

  124. "qqqzqizzqziqqqqqzqzz"

    8

    Returns: 54

  125. "qiiqqzwywqqvqiqiqiiiqziqxiiqvqzzxyqviqqqwq"

    23

    Returns: 53

  126. "qqquixqqqiqqqiq"

    3

    Returns: 60

  127. "kqqnjqiqtwqhquqnqqqqqoqiiqqiqqqqqqmqdqqmiqiqvnu"

    3

    Returns: 590

  128. "qr"

    2

    Returns: 0

  129. "iq"

    1

    Returns: 1

  130. "itqq"

    1

    Returns: 3

  131. "qqqqiqtiwqqxqqqqqq"

    8

    Returns: 32

  132. "qqiqspzqnixyqqsipiit"

    11

    Returns: 9

  133. "qqxqwqqq"

    8

    Returns: 0

  134. "xqqqqqyqtqqqe"

    12

    Returns: 1

  135. "wqqqovqpqqoqqqhqwqqirqrqigqqlrqyi"

    33

    Returns: 0

  136. "jmizlqqqqqqgqiiqiiqqqqqqqivqqijiqqiqqzqqiikku"

    27

    Returns: 42

  137. "sqofqqqqqq"

    9

    Returns: 1

  138. "iqtq"

    0

    Returns: 6

  139. "xfqqmuqiaaqqqqiiqiqndtyiqeiqquiqqiqqimqqaiop"

    4

    Returns: 322

  140. "qsitiiqt"

    1

    Returns: 13

  141. "qqzqqiizqqiqzzzzziqziqqqqiq"

    12

    Returns: 75

  142. "qqtsituqqqqiqiiiqsqvy"

    2

    Returns: 85

  143. "rqqqyqqqivqzqqqqvqqpxqqqqqqpiqqqqqpsqtqqsqqrtqq"

    33

    Returns: 22

  144. "qzyqqiqqqqiqiiqqqqqqqvyvqzviiqiyqyqziqqqvvqi"

    11

    Returns: 275

  145. "qziqiqrqqsqiisvivqutqq"

    18

    Returns: 4

  146. "qqqiqqwqqiqqqwqqqqi"

    18

    Returns: 1

  147. "iqqyqiqqpiiqiqgqiquqvqiqqvqhqqqqz"

    4

    Returns: 255

  148. "qmrqtqzqisqiiqqqiqqqzlqiqiqiqyqiqqqiqqilq"

    30

    Returns: 15

  149. "qvqpqqqqqqxyqqrqqiqit"

    2

    Returns: 131

  150. "eqqngomiqmmqjgqimqqqmqiqiqqqxitvqqiy"

    19

    Returns: 29

  151. "qqqqqqqqyqq"

    3

    Returns: 50

  152. "qiiqiehqqqqztqqqmgseqqqquqiqiiliqqkiqqquiq"

    13

    Returns: 161

  153. "yqqqtqqqqqpuoqqqvqrrwziztqqrqqoiqzqqoqmqquqzuiqvni"

    44

    Returns: 6

  154. "yzqqqxiqqyyzqqiqyqiyyxiqqxqzqqqyqqyqqqxqqiqqzqzz"

    32

    Returns: 52

  155. "qqqpiiqiiqqgyiqsqqqqqqqjqvqxquiuq"

    17

    Returns: 36

  156. "kqqqpqqjizpiqmqiiqqquqqwpm"

    25

    Returns: 1

  157. "qqqqiiqiiqqvq"

    0

    Returns: 81

  158. "uqwiqqqqqrzqqqqqrqiiiqqqqqqq"

    2

    Returns: 312

  159. "sqisniirniqqiqpqjqzpqqqiqnqqqqqiqbsnkijqqiqqqqi"

    14

    Returns: 199

  160. "qqixqqhiqtqqqnioqiiqqqjiqq"

    7

    Returns: 91

  161. "uqqqwqqqjqiqlzqqqqqqi"

    14

    Returns: 7

  162. "zqqqyiziqqqyiiqqzqyiyqqyz"

    3

    Returns: 130

  163. "mqqtqqqqzqvqriqqqimqqippq"

    24

    Returns: 1

  164. "sqiqqqqrmpqqeqqqqqgiqiqdqqdqqqqqqkqwqqt"

    31

    Returns: 8

  165. "iqr"

    3

    Returns: 0

  166. "wqxyxwqqxiyqqiqqiqqqqiq"

    19

    Returns: 4

  167. "qqqmqjqqklkpq"

    9

    Returns: 4

  168. "iuqqdqxmyiqqqqqqqiyjqinqimq"

    15

    Returns: 18

  169. "qwziqqqiyqqiiq"

    12

    Returns: 2

  170. "iqqqzxme"

    3

    Returns: 5

  171. "yqpqssqszowzq"

    3

    Returns: 16

  172. "qqqqiiqiqoqqnqqwqiqqiqqq"

    13

    Returns: 35

  173. "isqqrioq"

    3

    Returns: 5

  174. "iiiqqiqqqzqqzqi"

    10

    Returns: 9

  175. "zzqqqiyzqqqzqzqqiyyzqyzqq"

    25

    Returns: 0

  176. "qvwiiiqxwquixy"

    13

    Returns: 1

  177. "qqqqqzzqiqqqziqzqiqqqqzq"

    22

    Returns: 2

  178. "qqqqq"

    1

    Returns: 16

  179. "qqiqiqqzqqqxiwqqqxxwwqqqqwziqqwxq"

    28

    Returns: 5

  180. "qqqgiiqqvqqiimiaiqwiiq"

    21

    Returns: 1

  181. "aaabbb"

    3

    Returns: 5

  182. "aaabbb"

    6

    Returns: 0

  183. "aaaaaaaaaa"

    3

    Returns: 49

  184. "abbbccc"

    3

    Returns: 6

  185. "aaaaabbbbbccccc"

    5

    Returns: 34

  186. "waefawefdz"

    4

    Returns: 6

  187. "aaaa"

    4

    Returns: 0

  188. "aaaaaaabbv"

    3

    Returns: 21

  189. "aaaabbbbccd"

    4

    Returns: 13

  190. "abcdeabcdabcdeabcdabcdeabcdabcdeabcdeeeeabcdeabcde"

    50

    Returns: 0

  191. "aaaabbbbcccc"

    4

    Returns: 22

  192. "aaaaaaaaaaaaaaa"

    3

    Returns: 144

  193. "aaaaabbbbb"

    2

    Returns: 32

  194. "aabbbbcccccc"

    5

    Returns: 17

  195. "aabbccddeeff"

    2

    Returns: 18

  196. "zzzzzzzzzzza"

    3

    Returns: 65

  197. "aaabbbb"

    4

    Returns: 5

  198. "aaaaaaasssssssdddddddd"

    11

    Returns: 41

  199. "aaabbb"

    2

    Returns: 8

  200. "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"

    30

    Returns: 400

  201. "ababababababababa"

    4

    Returns: 85

  202. "aaaaaaaa"

    0

    Returns: 64

  203. "aabb"

    2

    Returns: 2

  204. "dhgahjdgjagdjagjdgajdgajhdgjhgdhjagdjhagdjhag"

    13

    Returns: 206

  205. "abcdezzzzzzz"

    4

    Returns: 14

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: