Statistics

Problem Statement for "ColorfulChocolates"

Problem Statement

Beaver Bindu has some chocolates arranged in a row. The wrapping of each chocolate has a single color. Multiple chocolates can share the same color. In this problem, each of the possible colors is represented by an uppercase letter. You are given a String chocolates. For each i, the i-th chocolate (0-based index) in the row has the color chocolates[i].

The spread of a row of chocolates is the maximum number of adjacent chocolates that all share the same color. Formally, the spread can be defined as the maximum value of (j-i+1), where i <= j and all the chocolates in the positions between i and j, inclusive, have the same color.

You are also given an int maxSwaps. Bindu can swap any two adjacent chocolates. She has decided to make at most maxSwaps such swaps.

Return the maximum spread she can obtain.

Definition

Class:
ColorfulChocolates
Method:
maximumSpread
Parameters:
String, int
Returns:
int
Method signature:
int maximumSpread(String chocolates, int maxSwaps)
(be sure your method is public)

Constraints

  • chocolates will contain between 1 and 50 characters, inclusive.
  • Each character in chocolates will be an uppercase letter ('A'-'Z').
  • maxSwaps will be between 1 and 2500, inclusive.

Examples

  1. "ABCDCBC"

    1

    Returns: 2

    One optimal solution is to swap chocolates at positions 2 and 3, obtaining the row "ABDCCBC", which has spread 2.

  2. "ABCDCBC"

    2

    Returns: 3

    The only optimal solution is to produce the row "ABDCCCB".

  3. "ABBABABBA"

    3

    Returns: 4

    The row "ABBBBAABA" can be produced with 3 swaps.

  4. "ABBABABBA"

    4

    Returns: 5

    An optimal solution is to produce the row "AABBBBBAA".

  5. "QASOKZNHWNFODOQNHGQKGLIHTPJUVGKLHFZTGPDCEKSJYIWFOO"

    77

    Returns: 5

  6. "ZWYZ"

    2

    Returns: 2

  7. "STDCJAHMSUXMPVNGGSCGXLFCFBJ"

    2

    Returns: 3

  8. "RQNKVRWVAKQVIEKDRQLJUS"

    5

    Returns: 3

  9. "HWEZHPUZYAYMNZGUSWRBWJCUZCCJZTWIPCKWTEYUGWGTVON"

    59

    Returns: 6

  10. "ETIPVERAHABCWMTAWPUAPOIOUBJIOBVUU"

    14

    Returns: 4

  11. "SKAURDVVZH"

    32

    Returns: 2

  12. "FFUHVKPJEQUOGYLCURMMBOGUREPTNFVTKRAFB"

    23

    Returns: 4

  13. "HKNVRLJVFAHSDYAZRGQKUVHPFYRNZJDIUQGNB"

    16

    Returns: 3

  14. "HRSBUSDTJKLWGGDVLEOYFYEOUUUHYJRHAJIWDNRPZ"

    19

    Returns: 4

  15. "FIQCVURWAPAQJWKSUVJBXVLT"

    15

    Returns: 3

  16. "MPYOAEYTIVPZRRQTHBQTTKOFMLCXGEYSUXIWDIPL"

    13

    Returns: 4

  17. "NXYDRGHHBA"

    28

    Returns: 2

  18. "HFDLFMQDGMAPIFZATDHGBFLUNSBPVUFEAKSFYKKFWNW"

    74

    Returns: 7

  19. "VGLZNTCTFWGZXXUREBTPTANDLUZYQFSMMELZZPUGLDGKACD"

    51

    Returns: 5

  20. "KGCKWIDKWJVXKMSRZXZJZBPEHOCFPQJCYLMUVRHRACPLRJEQ"

    12

    Returns: 4

  21. "CFGRMPHQVWGGYERLBP"

    7

    Returns: 3

  22. "GFMVSDGWWMBYUHPGXWW"

    16

    Returns: 4

  23. "FCT"

    2

    Returns: 1

  24. "GMKKWRPJOJ"

    56

    Returns: 2

  25. "ECDFFABAFEAEBBFABAABEDAFFBCCDABBAEEACFEFBFEAEBBDBB"

    126

    Returns: 13

  26. "BAAABBCCDDDDCDDAACADBCCBDDDCCDDDADABACADCDDADCADAA"

    113

    Returns: 19

  27. "CBDBACDCBCCBCCDCADCCCBCBDDBADABCBADBCDDABBBDDACADA"

    80

    Returns: 15

  28. "BBACCABACACAACAACBCCCCAABAAABBCCCABCBAACBACBAACABB"

    143

    Returns: 20

  29. "EEEAADADABCECDCEDCEGDFEGDAGGCCDEEBCEECFCBAABCAGFCB"

    91

    Returns: 11

  30. "FFECCEADDDCEDEAFACCDCFFABDDACDDAAACCCDEFAEBDDAADCA"

    108

    Returns: 13

  31. "CBABBBCBCACCBBCABBACAAABABBACCCABCBABBCACBCAAABCCB"

    158

    Returns: 19

  32. "HCAGGAHFBHFFFDHCAFDHHEEHCFAFCFDBHDAGEHDFGACEDBGEGB"

    60

    Returns: 9

  33. "ECGDAFBBDEFEDCDAFEACBAACBBCAGCEEEEAECGEEBABFACDFEE"

    102

    Returns: 13

  34. "EFFDEGCEGGGBBEDCEAGDFFGFADECACFCGBEDAEFGDCADAEFCCE"

    126

    Returns: 10

  35. "HKJIKDSZLRXKNSPPNAMTPXDLOVUEGLBOVLYGQS"

    27

    Returns: 4

  36. "CTDNLTDFGIBMFFCHLCJFRYTOILKCPRLTKQJXMODUWGHDNLLYNU"

    67

    Returns: 6

  37. "MXKEPAVPQUENHXVWTCPLTQZOWQBOKTXWQJCHLXXCUDRBCMZVOQ"

    46

    Returns: 5

  38. "JJHZFXATIVSGMBJTNISPCXGFZUEULVCUEMULJWETSXAGAJZNRU"

    25

    Returns: 5

  39. "WRMDRHINUFSOLEKYPJCJBBJHCUIRNCYLWMPNTZCNGUERAQPQZT"

    21

    Returns: 4

  40. "CXKLBGWUTASFWFWLAVOQBIWUJMLBOECSDOEEUAZPARWZYSKBNY"

    40

    Returns: 5

  41. "OJPKSBVVRCXKFLOKHQLWSETRDLCEBAXRJMCDPXYJZXTFKJRRZC"

    56

    Returns: 5

  42. "TIJLNWNRXPQPBETEWQFFSEYZPJSIIWYDEHOSEDLDTEUUINAGGH"

    19

    Returns: 3

  43. "AMLZDUTLEPMITTWLZCZDVDZRNPTUVBFXPTYUNRHUGTCZPANOCM"

    60

    Returns: 6

  44. "ZRVSEKMYHPGEGZCAMVJGBFKCUNRKRFGRWBJBLXBUMHASGCUVXG"

    45

    Returns: 4

  45. "ALOCHDURUBZNYAXBNWCJJKJDQNALKGPMTFRAKLTEMTSMVRNLNQ"

    61

    Returns: 5

  46. "WCECURCGEKXSDEJFOWYULTMXRDNERFYPHETBYVJEFIWKOGPCEQ"

    85

    Returns: 7

  47. "AAAABBABAABABBAABBAABAABBAABAAABAABBAABAAAAABAABBA"

    156

    Returns: 31

  48. "BAABBABBBAABAABAABAAAAAABAAABBBABBBABBAABAABABBABB"

    110

    Returns: 26

  49. "CBDBDBADADAACCBBAADACCBAABDDDACBCCCBDCAACAAADBBDCA"

    131

    Returns: 16

  50. "BABAAABBAAAABABAABBAAABABAABBBABBBBBBABAABAAABAAAA"

    188

    Returns: 28

  51. "NXIASZWQAGIX"

    4

    Returns: 2

  52. "CACBBCCDCCCEBCCCCCJJJCBBCKLBCBBCBSCSBWWWCWWCWCCCC"

    33

    Returns: 14

  53. "CBABBACBABABCCCCCAABBAACBBBBCBCAAA"

    8

    Returns: 7

  54. "AAABCD"

    1

    Returns: 3

  55. "ZZZZZZZ"

    3

    Returns: 7

  56. "QASOKZNHWNFODOQNHGQKGLIHTPJUVGKLHFZTGPDCEKSJY"

    1234

    Returns: 4

  57. "AAABBBBBBBBBBBBBAABB"

    1000

    Returns: 15

  58. "ZAZAZ"

    2

    Returns: 3

  59. "QASOKZNHWNFODOQNHGQKGLIHTPJUVGKLHFZTGPDCEKSJYIWFOO"

    2500

    Returns: 5

  60. "ABCDEFGABCDEFGABCDEFGABCDEFGABCDEFGABCDEFGABCDEFG"

    2500

    Returns: 7

  61. "AAAAA"

    1

    Returns: 5

  62. "AAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAABBBBB"

    50

    Returns: 15

  63. "A"

    2

    Returns: 1

  64. "ABCDBBVNBBB"

    6

    Returns: 5

  65. "AABBCCCCCFGFGFGFGSCDCDCDCDCDFGFGFGFYYYYSESEWWSESEG"

    2500

    Returns: 10

  66. "ABCDEFGHJIB"

    4

    Returns: 1

  67. "Z"

    2500

    Returns: 1

  68. "JWSMEADGLXDIUKWZGNXWSILWDJBWMGCFVLSHJUUKKTHDEEWBHW"

    1

    Returns: 2

  69. "CDUCACBC"

    2

    Returns: 3

  70. "ASDSDRGRGGEAAARRQWYUAAHAAUTNFAA"

    55

    Returns: 10

  71. "AACAAA"

    1

    Returns: 4

  72. "AABBCCDEFFGDTHBDBAADSBDDBSUSIDAPQZAIDTTYYAAZYYDBD"

    37

    Returns: 7

  73. "ABBACCADDAEE"

    2

    Returns: 2

  74. "ABACADAEAFAGADAFAGAVBABABBBBBBACADADAFA"

    50

    Returns: 13

  75. "DACDDBEDEEBCCECCCADDAEDBBAAEABEDBEEABDCCABEACECCCC"

    95

    Returns: 10

  76. "ABDDSCBSDXSFGFSSSDCVDSCSSXXASSSWCAXA"

    20

    Returns: 8

  77. "AABABABABABABCCCBBCBABCBACBACBBCBCCBCCCBACABCBCBC"

    6

    Returns: 7

  78. "A"

    1

    Returns: 1

  79. "Z"

    10

    Returns: 1

  80. "AABCBACAA"

    5

    Returns: 4

  81. "AAAAAAAAXA"

    1

    Returns: 9

  82. "ABBBBBBABBCABCBCBCAA"

    1

    Returns: 7

  83. "ZZZZZ"

    1

    Returns: 5

  84. "ABCDEFGHIJKLMNOPQRSTUVWXYZQBCDEFGHIJKLMNOPQRSTUV"

    2500

    Returns: 3

  85. "QASOKZNHWNFODOQNHGQKGLIHTPJUVGKLHFZTGPDCEKSWFOOWEE"

    2500

    Returns: 5

  86. "ABCDEFGABCDEFGABCDEFGAZZ"

    11

    Returns: 2

  87. "CCBBCBAABCCCBABCBCAA"

    91

    Returns: 8

  88. "ABCADAEA"

    2

    Returns: 3

  89. "ABCDEFAAAHIJAA"

    6

    Returns: 5

  90. "BABCDB"

    3

    Returns: 3

  91. "ABCDA"

    1

    Returns: 1

  92. "EDADGECCBDFAGGHIBDJFIFEHBFFJBICHGFDACCDJBAIBEJGAJ"

    5

    Returns: 3

  93. "ABABCAABBABBBBAAAABBBBAAAAABACADADDDADDDDAACCACADD"

    67

    Returns: 17

  94. "A"

    2500

    Returns: 1

  95. "ABCDASAFA"

    2

    Returns: 3

  96. "AABBBAAAABBBAAACCAA"

    14

    Returns: 8

  97. "ABCDEFA"

    2

    Returns: 1

  98. "AAAAA"

    5

    Returns: 5

  99. "YEHXIDONKPSZLVCNGMPKYTDAOP"

    50

    Returns: 3

  100. "CAAACCCCA"

    3

    Returns: 5

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: