Statistics

Problem Statement for "ArtShift"

Problem Statement

Let S[0], S[1], ..., S[N-1] be a sequence of colors, each of which is either black or white. An art shift is a permutation (P[0], P[1], ..., P[N-1]) of integers between 0 and N-1, inclusive. It can be used to create a new sequence from the given one. For each i, the integer P[i] represents the position of the character of the previous sequence that will appear in the i-th position of the new sequence. In other words, if an art shift P is applied to a sequence S, the resulting sequence is (S[P[0]], S[P[1]], ..., S[P[N-1]]).

Given a sequence S and an art shift P, we can obtain new sequences, where each next sequence is obtained from the previous one by applying the art shift P. All these sequences are said to be reachable from S using P.

For simplicity, a sequence of N colors can be represented as a String containing N characters, where the i-th character is 'B' if the i-th color in the sequence is black and 'W' if the i-th color is white. Consider an example, where the initial sequence is "WBWWB" and the art shift P = {1,0,2,4,3}. Then after the first application of P we get "BWWBW", after the second application we get "WBWWB" and after the next applications we get "BWWBW", "WBWWB", "BWWBW" and so on. Overall in this case there are 2 different sequences reachable from the initial sequence using the given art shift.

Given an initial sequence, return the maximum number of different sequences that are reachable from it by using a single art shift.

Definition

Class:
ArtShift
Method:
maxShifts
Parameters:
String
Returns:
int
Method signature:
int maxShifts(String sequence)
(be sure your method is public)

Constraints

  • sequence will contain betweeen 1 and 30 characters, inclusive.
  • Each character in sequence will be 'B' or 'W'.

Examples

  1. "BW"

    Returns: 2

    We can use an art shift of {1,0} to reach "WB" and then "BW" again for a total of two different reachable sequences.

  2. "BBBWBBB"

    Returns: 7

  3. "BWBWB"

    Returns: 6

    A possible art shift that allows us to reach 6 different sequences is: {1,2,0,4,3}.

  4. "WWWWWWWWW"

    Returns: 1

    It does not matter what art shift we use; the sequence will always stay the same.

  5. "BBBWBBBBBWWW"

    Returns: 60

  6. "BBBBBWBBBBBBWBBBBBBBWBBBBBBBBB"

    Returns: 990

  7. "BWBWBWBWBWBWBWBWBWBWBWBWBWBWBW"

    Returns: 4620

  8. "W"

    Returns: 1

  9. "BBBBBBBBBBB"

    Returns: 1

  10. "WWWWWWWWWBBWB"

    Returns: 60

  11. "B"

    Returns: 1

  12. "BB"

    Returns: 1

  13. "BW"

    Returns: 2

  14. "BBB"

    Returns: 1

  15. "WWB"

    Returns: 3

  16. "BBBB"

    Returns: 1

  17. "BWWW"

    Returns: 4

  18. "WWBB"

    Returns: 4

  19. "WWWWW"

    Returns: 1

  20. "WWBWW"

    Returns: 5

  21. "WBBWW"

    Returns: 6

  22. "BBBBBB"

    Returns: 1

  23. "BBBBBW"

    Returns: 6

  24. "WBWBBB"

    Returns: 6

  25. "BBWWWB"

    Returns: 6

  26. "WWWWWWW"

    Returns: 1

  27. "WWWWBWW"

    Returns: 7

  28. "WWWWBBW"

    Returns: 12

  29. "BWBBWWW"

    Returns: 12

  30. "WWWWWWWW"

    Returns: 1

  31. "WBWWWWWW"

    Returns: 8

  32. "BBBBBWBW"

    Returns: 15

  33. "BWBWBBWB"

    Returns: 15

  34. "BBBBWWWW"

    Returns: 15

  35. "WWWWWWWWW"

    Returns: 1

  36. "WWWWWWBWW"

    Returns: 9

  37. "WWBBBBBBB"

    Returns: 20

  38. "BBBWBWBWB"

    Returns: 20

  39. "WBWWBWBBW"

    Returns: 20

  40. "WWWWWWWWWW"

    Returns: 1

  41. "BBBBBBWBBB"

    Returns: 10

  42. "WWWWBWWWBW"

    Returns: 21

  43. "BBWWBBBBWB"

    Returns: 30

  44. "WBWBWBBWBB"

    Returns: 30

  45. "WWBBWWBWBB"

    Returns: 30

  46. "WWWWWWWWWWW"

    Returns: 1

  47. "BBBBBWBBBBB"

    Returns: 11

  48. "BBBBBBBWBBW"

    Returns: 30

  49. "BBBWBBBWBWB"

    Returns: 30

  50. "BWWWBBWBWWW"

    Returns: 30

  51. "BWBBWBWBWWB"

    Returns: 30

  52. "WWWWWWWWWWWW"

    Returns: 1

  53. "BBBBWBBBBBBB"

    Returns: 12

  54. "WBBBBBBBWBBB"

    Returns: 35

  55. "BWBWWWWWWBWW"

    Returns: 60

  56. "WBBBWBBBBBWW"

    Returns: 60

  57. "BBWBWBBWBWWB"

    Returns: 60

  58. "BBBWBWWWWBBW"

    Returns: 60

  59. "WWWWWWWWWWWWW"

    Returns: 1

  60. "WWWWWWBWWWWWW"

    Returns: 13

  61. "WWWWWWBWBWWWW"

    Returns: 42

  62. "WBBBBBBBBWWBB"

    Returns: 60

  63. "WBBBBWBWWBBBB"

    Returns: 60

  64. "WBBBWBBWBWBWB"

    Returns: 60

  65. "BBBWWBBWWBWWB"

    Returns: 60

  66. "BBBBBBBBBBBBBB"

    Returns: 1

  67. "BBBBBBBBBWBBBB"

    Returns: 14

  68. "WWWWWWWWBWBWWW"

    Returns: 45

  69. "WWWBWWBWWWBWWW"

    Returns: 84

  70. "WBWWBWBWWWBWWW"

    Returns: 84

  71. "WWBWBBBWBWBBBB"

    Returns: 84

  72. "BWWBWWWBWBWWBB"

    Returns: 84

  73. "WWWBBBWBWBWBWB"

    Returns: 84

  74. "BBBBBBBBBBBBBBB"

    Returns: 1

  75. "WBWWWWWWWWWWWWW"

    Returns: 15

  76. "WWWWWWWWWWWWBWB"

    Returns: 56

  77. "BBBBBBBBWWBBBWB"

    Returns: 105

  78. "WBBWWWWWWWBWWBW"

    Returns: 105

  79. "BBBWWBWBBBBBWWB"

    Returns: 105

  80. "WBBWWBBBWBBBBWW"

    Returns: 105

  81. "BBWBWWWBBWWBBBW"

    Returns: 105

  82. "BBBBBBBBBBBBBBBBBBBBBBBBB"

    Returns: 1

  83. "WWWWWWBWWWWWWWWWWWWWWWWWW"

    Returns: 25

  84. "BBBBBBBBBBBBBBBBBBWBBBWBB"

    Returns: 156

  85. "WWWBWWWWWWWWWWWWWWWWWWBBW"

    Returns: 504

  86. "BBWWWBBBBBBWBBBBBBBBBBBBB"

    Returns: 1260

  87. "BBBBBBBBBBBBWWBWWWBBBBBBB"

    Returns: 1260

  88. "BWWWBBBBBBBBBBWWBBBBWBBBB"

    Returns: 1260

  89. "BWBWBWBBBWBBBWBWBBWBBBBBB"

    Returns: 1260

  90. "WBWWBWWWWWWWWWBBWWWBWBBWB"

    Returns: 1260

  91. "WBBWBWWBBBWWWWBBBBBBBWBBB"

    Returns: 1260

  92. "BWBBBBWBBWBWBBBWWBBWWWBBW"

    Returns: 1260

  93. "WBWBBWBBBWBWWWWWBBWBBWWWW"

    Returns: 1260

  94. "WBBWWWWWBBWWBBWWBBBBWBBWB"

    Returns: 1260

  95. "WWWWWWWWWWWWWWWWWWWWWWWWWW"

    Returns: 1

  96. "WBBBBBBBBBBBBBBBBBBBBBBBBB"

    Returns: 26

  97. "BBBBBBBBWBBBBBBBBBBBBBBBWB"

    Returns: 165

  98. "WWWWWWWWWWWBWWWWWWBWWWWWBW"

    Returns: 630

  99. "BBWBBBWBBBBBBBBBWBBBBBBBBW"

    Returns: 1260

  100. "BWBBBBWBBBWBBBWBBBWBBBBBBB"

    Returns: 1260

  101. "WWWBWBWWBBWWWWWWWBWWBWWWWW"

    Returns: 1260

  102. "WBBBWWWWWBWWBWWWWWBWWWWWBW"

    Returns: 1260

  103. "WWWWWBWWWWWBWWWBWWBWWBBWBB"

    Returns: 1260

  104. "WBBWWBWWWWWBWWWWWBBWWBWBBW"

    Returns: 1260

  105. "WBBBWBWWBBWWBWBWWBWWWWWWWB"

    Returns: 1260

  106. "BBWWWBBBWBWBWWBWWWWBBWBWWW"

    Returns: 1260

  107. "BWWBWBWBBWBBWWBBWWBWBWBBWB"

    Returns: 1260

  108. "WWBBWWWWBWBWBBBBWWBBBWWBWB"

    Returns: 1260

  109. "BBBBBBBBBBBBBBBBBBBBBBBBBBB"

    Returns: 1

  110. "BBBBBBBBBBBBBWBBBBBBBBBBBBB"

    Returns: 27

  111. "BBBBBWBBBBBBBBWBBBBBBBBBBBB"

    Returns: 182

  112. "WBBBWBBBBBBBBBBBBWBBBBBBBBB"

    Returns: 693

  113. "BWBBBBBBBBBWBBBWBBBBWBBBBBB"

    Returns: 1540

  114. "WWWWWBWBWWBWWWWWWWWWWWBWWBW"

    Returns: 1540

  115. "WWBBWWWWWBWWWWWWWWWBWWWWBWB"

    Returns: 1540

  116. "BBWBBBBWBBBWBWBBBBBBBBBWWBW"

    Returns: 1540

  117. "WBBWBWBBBBBWWBBBWBBWBBWBBBB"

    Returns: 1540

  118. "WBWWWWWBWWBWWBBBBWBWWWWWWWB"

    Returns: 1540

  119. "BBBWWBBWBBBWBBWWWBWBWBBBBWB"

    Returns: 1540

  120. "BBWBWWWWWWBWWBWBWWWWBWWBBBB"

    Returns: 1540

  121. "WWWBWWWBBBBWWWBWWBWBBBBWWBW"

    Returns: 1540

  122. "WWBBBBWWBBWWBWBBWBWBBWWWWBW"

    Returns: 1540

  123. "WWWWWWWWWWWWWWWWWWWWWWWWWWWW"

    Returns: 1

  124. "WWWWWWWWWWWWWWWWWWWWWWBWWWWW"

    Returns: 28

  125. "BBBBBBBBBBBWBBBBBBBBBBBBBBBW"

    Returns: 195

  126. "WWWWWBWWWWWWWWBWWWWWWWWBWWWW"

    Returns: 792

  127. "WWWWBWBWWBBWWWWWWWWWWWWWWWWW"

    Returns: 1540

  128. "BWBBWBBBBBBBBBBBBBBBWBBWBBBW"

    Returns: 2310

  129. "WWWWWWWWBWWWWWBBBWWWBWWWBWWW"

    Returns: 2310

  130. "WBWBWBBWWWBBBBBBBBBBBBWBBBBB"

    Returns: 2310

  131. "WWWWWBWWWWWWWWWBWBWWBWWBBWBB"

    Returns: 2310

  132. "WBWBBWBBWWWBWWWWWWWBWWWBWWBW"

    Returns: 2310

  133. "WWBWWBWWWWWWWWWWBWWBBWBWBBBB"

    Returns: 2310

  134. "BWBBBWWWWWBBBBWBBBBBWWBBBWBW"

    Returns: 2310

  135. "WWBWBWBWBBBWWWWWWWWWBBBWBWBB"

    Returns: 2310

  136. "WBWBWWWBBBBWBBBBWBWWWWWBWWWB"

    Returns: 2310

  137. "BBBBWWBBWWWWWWWWBBBBBBWBWBWW"

    Returns: 2310

  138. "WWWWWWWWWWWWWWWWWWWWWWWWWWWWW"

    Returns: 1

  139. "WWWWWWWWWWWWWWWWWWWWWWWWWWBWW"

    Returns: 29

  140. "WWWWWWWWWBWWWWWWWWWWWWWWWWWBW"

    Returns: 210

  141. "WWWBWWWWWWWWWWWWWWWBWWWWWWWBW"

    Returns: 819

  142. "WWWWWWWWWBWBBWWWWWWWWWWBWWWWW"

    Returns: 2520

  143. "WWWWWWBWWWWBWWWBWBWWWWWWWWWWB"

    Returns: 2520

  144. "WBWWWWWWWBWBWBWWBWWWWBWWWWWWW"

    Returns: 2520

  145. "WBBBBBBBBBBBWBBBBWBWBWBWBBWBB"

    Returns: 2520

  146. "BBBBBBBBWWWBBBBBBBBBWWBWBBBWW"

    Returns: 2520

  147. "BWWWBWWWWWBBWWBBWBWWBWWWWWWWB"

    Returns: 2520

  148. "BBBWBBBBBBWBBWBBBWBBWBWWWWBBW"

    Returns: 2520

  149. "BBWBBWBWBBWBWBBWBBWWBBWWBBBBW"

    Returns: 2520

  150. "WBWBBBBWWBBBBBBWWBWWWWBBBWBWB"

    Returns: 2520

  151. "WBWBBBBBBWWBBWBBWBWWWBBWBBWWW"

    Returns: 2520

  152. "BBBWWWWBWBBWWWBWWBBBWBBWBWBWB"

    Returns: 2520

  153. "BBBBBBBBBBBBBBBBBBBBBBBBBBBBBB"

    Returns: 1

  154. "WWWWWWWWWWWWWWWWWWWWWWBWWWWWWW"

    Returns: 30

  155. "BBBBBBBBBBWBBBBBBBBBBBBBWBBBBB"

    Returns: 221

  156. "BBBBBWBWBBWBBBBBBBBBBBBBBBBBBB"

    Returns: 990

  157. "BBBBBBWBBBBBBBBWWBBBBBBBBWBBBB"

    Returns: 2520

  158. "WBBBBWBBBBBBWWBBBBBBBBBWBBBBBB"

    Returns: 4620

  159. "BBBBBWBBWBBBBBBWBBBWWBBBBBBBWB"

    Returns: 4620

  160. "BWBWWBWWWBWBWWWBWWWWWWWWBWWWWW"

    Returns: 4620

  161. "BBWBBBBBBBBBWBBBWBBBBBWWBWBBWW"

    Returns: 4620

  162. "BWBBBBBBWBBWBBBBWBBWBBBWBWBWBW"

    Returns: 4620

  163. "WBWWWWWBBWWWWBBBWWWWBBWWWBBWWW"

    Returns: 4620

  164. "BBBBBWBWBBWBBBBWBBWWWWBWBBBWBW"

    Returns: 4620

  165. "BBBBBWWBWBWBWWWWBWWBBWWWWWBWWW"

    Returns: 4620

  166. "BWBWBBBBWWWBWBBWWWWWBWWWWBWWBB"

    Returns: 4620

  167. "WWBBBWBBWWWBBBWBWWWBWBBWWBWWBW"

    Returns: 4620

  168. "BBBBBBBBWWBWBWBWWWBWBWWWBWBWWW"

    Returns: 4620

  169. "BBBBBBBBBBBBBBBBB"

    Returns: 1

  170. "BBBBBBBBBBBWBBBBB"

    Returns: 17

  171. "BWBBBBBBWBBBBBBBB"

    Returns: 72

  172. "BWWWWWWWBWWBWWWWW"

    Returns: 140

  173. "WWWBWWWWWBWWWBWWB"

    Returns: 210

  174. "WWWWBWWWWWBBBWWWB"

    Returns: 210

  175. "WBWBBBWBBBWBBWBBW"

    Returns: 210

  176. "WBBBBBWWBBBWBWWWB"

    Returns: 210

  177. "BWBBWBWBWWWWBWBWB"

    Returns: 210

  178. "BBBBBBBBBBBBBBBWWWWWWWWWW"

    Returns: 1260

  179. "WWWWWWWWWWWWBBBBBBBBBBBBBBBBB"

    Returns: 2520

  180. "BBBBBBBBBBBBBBBBBBBBBBBBBBBBWW"

    Returns: 221

  181. "WWWWWB"

    Returns: 6

  182. "WWWWWWWWWWWWWWWWWWWWWWWWWWBBBB"

    Returns: 2520

  183. "WWWWWWWWWWWWWWWBBBBBBBBBBBBBBB"

    Returns: 4620

  184. "WWWWWWWWWWWWWWWWWWWWWWWWWWBWWW"

    Returns: 30

  185. "WBWBWBWBWBWBWBWBWBWBWBWBWBWBBB"

    Returns: 4620

  186. "BBBBBBBBBBBBBBBBBBBBBBBBBBBBW"

    Returns: 29

  187. "BBWWWWWWWWWWW"

    Returns: 42

  188. "WWBBBBBBBBBBBBBBBBBBBBBBBBBBBB"

    Returns: 221

  189. "WWWWWBBBBB"

    Returns: 30

  190. "BBBBBBBBBBBBBBBWWWWWWWWWWWWWWW"

    Returns: 4620

  191. "BBBBBBBBBBBBBBBBBBBBBBBBBBBWW"

    Returns: 210

  192. "WWBBBBBBBBBBBBBBBB"

    Returns: 77

  193. "BBWW"

    Returns: 4

  194. "WBWBBBBBBBWBWWWBBBWBBBWBWBW"

    Returns: 1540

  195. "BBBBBBBBBBBBWWWWWWWWWWWWWWWWW"

    Returns: 2520

  196. "BBBBBWWWWW"

    Returns: 30

  197. "BBBBBBBBBBBWWWWWWWWWWWWW"

    Returns: 840

  198. "WBWBWBWBWBWBWBWBWBWBWBWBWBWBWB"

    Returns: 4620

  199. "WWWWWWWWWWWWWWWWWWWWWWWWWWWBB"

    Returns: 210

  200. "BWBWBWBWBWBWBWBWBWBWBWBWBWBWBB"

    Returns: 4620

  201. "BBBBBWBBBBBW"

    Returns: 35

  202. "WWBBBBBBBBBBB"

    Returns: 42

  203. "BWBW"

    Returns: 4

  204. "WBWB"

    Returns: 4

  205. "WWWWWWWWWWWWWWWWBBBBBBBBBBBBB"

    Returns: 2520

  206. "WWWBBBBBBBBBBBBBBBBBBBBBBBBBBB"

    Returns: 990

  207. "WWWWWWWBBBBW"

    Returns: 60

  208. "BBWWWWWWWWWWWWWWWWWWWWWWWWWWW"

    Returns: 210

  209. "BBBBBBBBBBBBBBBBBBBBBBBBBBWWWW"

    Returns: 2520

  210. "WWBBBBBBBBB"

    Returns: 30

  211. "WWWWWWBBBB"

    Returns: 30

  212. "BBBBBBBBBBBBBBBBBWWWWWWWWWWWW"

    Returns: 2520

  213. "BBBBBBBBBBBBBBBWWWWWWWWWWWWWW"

    Returns: 2520

  214. "WWWWWWWWWWWWWBBBBBBBBBBBBBBBB"

    Returns: 2520

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: