Statistics

Problem Statement for "PenguinPals"

Problem Statement

Penguin Pals is a match making service that matches penguins to new friends, using the following procedure:

  1. Each penguin is asked a single question: "Do you prefer the color blue, or the color red?"
  2. All penguins are arranged so that they stand on a circle, equally spaced.
  3. The organizers draw some straight lines, connecting some pairs of penguins. Each penguin may only be connected to at most one other penguin. Two penguins cannot be connected if they prefer a different color.
  4. Each penguin who is connected to some other penguin follows the line to find their match.


The only problem with the above system was that it allowed penguins to collide if two lines crossed each other. Therefore, a new additional rule was adopted: no two lines may cross. Penguin Pals now has some penguins arranged on a circle (after step 2 of the above procedure). They need to know the maximum number of pairs of penguins they can create.


You are given a String colors whose i-th character represents the prefered color of the i-th penguin (0-based index) in the circular arrangement. The i-th character is 'R' if the i-th penguin prefers red and 'B' if the i-th penguin prefers blue. Return the maximum number of matched pairs that can be formed.

Definition

Class:
PenguinPals
Method:
findMaximumMatching
Parameters:
String
Returns:
int
Method signature:
int findMaximumMatching(String colors)
(be sure your method is public)

Constraints

  • colors will contain between 1 and 50 characters, inclusive.
  • Each character of colors will be either 'R' or 'B'.

Examples

  1. "RRBRBRBB"

    Returns: 3

    In this picture the penguins have been colored in their preferred color.

  2. "RRRR"

    Returns: 2

  3. "BBBBB"

    Returns: 2

  4. "RBRBRBRBR"

    Returns: 4

  5. "RRRBRBRBRBRB"

    Returns: 5

  6. "R"

    Returns: 0

  7. "RBRRBBRB"

    Returns: 3

  8. "RBRBBRBRB"

    Returns: 4

  9. "B"

    Returns: 0

  10. "BRBRBRBRBRB"

    Returns: 5

  11. "RBRBRBRBRBR"

    Returns: 5

  12. "RRRBBBRRRBBBRBRBRBRB"

    Returns: 9

  13. "RR"

    Returns: 1

  14. "BB"

    Returns: 1

  15. "RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR"

    Returns: 25

  16. "BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB"

    Returns: 25

  17. "RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR"

    Returns: 24

  18. "BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB"

    Returns: 24

  19. "RBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRB"

    Returns: 24

  20. "BRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBR"

    Returns: 24

  21. "RBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBR"

    Returns: 24

  22. "BRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRB"

    Returns: 24

  23. "RRRRRBBBBBRRRRRBBBBBRRRRRBBBBBRRRRRBBBBBRRRRRBBBBB"

    Returns: 24

  24. "RBRBRBRBRBRBRBRBRBRBRBRRBRBRBRBRBRBRBRB"

    Returns: 19

  25. "RB"

    Returns: 0

  26. "BR"

    Returns: 0

  27. "RBR"

    Returns: 1

  28. "BRB"

    Returns: 1

  29. "BRRB"

    Returns: 2

  30. "RBRRRRRRBRRBRRBRBBRRRR"

    Returns: 11

  31. "BBBBBBBBBBBBBB"

    Returns: 7

  32. "RBRBBRBRBBRBRBRBBRBRBRBBRBRBRBRBR"

    Returns: 16

  33. "BBRBBRRBBBRR"

    Returns: 5

  34. "BBRRBBBRBRBBRBBBRBBBBBRRBBBB"

    Returns: 14

  35. "RRRRRRRRRRRRRRRRRRRRRRBB"

    Returns: 12

  36. "RBBRBBRBBBBBBBBB"

    Returns: 7

  37. "RBBBBBBBBBBBBBBBBBBBBBBBBBBRBR"

    Returns: 14

  38. "BBBRBBBBRRBBBRRB"

    Returns: 7

  39. "RRRRRRRRRRRRRRRRRRRRRRRRBRRRRRRRRRRRRRRRRRRRRRRRRR"

    Returns: 24

  40. "RRRRRRRBRRRRBRBRRRRRBRRRRRRRRBRBRRBRBRRRRBBRBRRB"

    Returns: 23

  41. "BRBBBBBBBBRRRRBRBRRRRRB"

    Returns: 11

  42. "BRRRBRBRBRRRRRRRBBRRRBRRRRBRRR"

    Returns: 14

  43. "BBBBBBBBRBBBBBRRBBBBBBBBBBBBBBBBBBBBBBBB"

    Returns: 19

  44. "BRRBRRRRRRBRRRRRRBRRBRBRRRBRRRBRRRRBRRBR"

    Returns: 19

  45. "RRRRRRRRRRRRRRBRRRRRRRRRRRRRRRRRRBRRBRRRRRR"

    Returns: 21

  46. "RRRRRRBRBRRRBRBRRRRBRB"

    Returns: 10

  47. "BRBBBBBRBBBBBBBB"

    Returns: 7

  48. "RBBBBBRRRBBRBRBRBRBBBRRRB"

    Returns: 12

  49. "RRRBBRR"

    Returns: 3

  50. "RRRBBBRRRBBBRRRBBBRRRBBBRRRBBBRRRBBBRRRBBBRBRBBBBB"

    Returns: 24

  51. "BRBBBBRRBBRBRBBRRRRRBRBBRRRBBBBRRRBBBRBRBBBBRBRRBR"

    Returns: 24

  52. "RRBRBRBBRRBRBRBBRRBRBRBBRRBRBRBBRRBRBRBBRRBRBRBB"

    Returns: 23

  53. "RRRRBBRBBRBRBRR"

    Returns: 7

  54. "RRBBRRBBBRBRRBRBRBRBRBRBRBRBBRRBRBRBRBBBBBBBBRRRRB"

    Returns: 24

  55. "BRBRRBBRRRRBRBRBBBBRRBRRRBBRBRBBRRBBRBBRRBB"

    Returns: 21

  56. "RRRRRRRRRRBBBBBBBBBBRRRRRRRRRRBBBBBBBBBBRRRRRRRRRR"

    Returns: 25

  57. "RRRRBBBBBRRBRBRBRRRRBBR"

    Returns: 11

  58. "RBRBRBRBRBBBBBRRRRRRBRBRBRBRBRBRBRBRBRBRBRBRBRBRB"

    Returns: 24

  59. "RRRBBBRBRBBRBBRRRRRRRRBBBRRBRBRBRRRRBRBBBRRRBBRRB"

    Returns: 24

  60. "RRRBRBRBRBRBBBBBRR"

    Returns: 8

  61. "RBBRRBBRRRRBBRBRBRBRBRRBBRBBRRBRBBRBRBRBRBRBRRRRR"

    Returns: 24

  62. "RRBBRRBB"

    Returns: 4

  63. "RBRRBRRRBRRRRBBRBRBRBRBRBRBRBRBRBRBRBBBBBRRRRRRRRR"

    Returns: 24

  64. "RRBB"

    Returns: 2

  65. "RBRBBRRRRRRBBBB"

    Returns: 7

  66. "RRRBBR"

    Returns: 3

  67. "RBRBRBRBRBBRBRBRBBRBRBBBRBRBBRBRBRBBRBBBRBBBRBB"

    Returns: 23

  68. "RRRRRRRBBRBRRBRRRRR"

    Returns: 9

  69. "RRRRRRB"

    Returns: 3

  70. "RBBR"

    Returns: 2

  71. "BRRBBRBRBRRBBRBRBRRBBRBRBRBBRRBRBRBRBRBRRBRBRBRBRB"

    Returns: 24

  72. "RBRBBBRBRBR"

    Returns: 5

  73. "RBRBBRBRRRBRRRBRRBRBRRRBRRBBBR"

    Returns: 15

  74. "RRRRRRRRRRRRRRBBBBBBBBRRRRRRRRBBBBBBBBBBBBBBBBBB"

    Returns: 24

  75. "RBBRRBRBBRRRBBBRRRRRBRBBRRBRRRBBBRBBBBBBRBBRRBRBRB"

    Returns: 25

  76. "RBRRBBBRBRBRRBBBRRBRBBBRRRBBBRRBRBRBRRBBBBRRBRBBRB"

    Returns: 24

  77. "BRRBRRB"

    Returns: 3

  78. "RBBRBBRRRB"

    Returns: 4

  79. "RBRBBBRBRB"

    Returns: 4

  80. "RBRBRBRBRRBRRRBBBBBRRBRBBRBRBRBBBRRBBBRRRRBBRBBRRB"

    Returns: 24

  81. "RBBRRRRRBB"

    Returns: 5

  82. "RBBRRRRBRBBRBRRBBRBRBRRRBRBBBRBRBBRBRBRBRBRBBRBRB"

    Returns: 24

  83. "RBRB"

    Returns: 1

  84. "RBRRRRBBBBRRBRBRBBBBBRBRRRRRRBBBRRBBRRRRBBBRRRRRRR"

    Returns: 24

  85. "RBRRRBRRBRBRBRBRBRRRRBRBRBRBRBRBRBRBRBBRRBBRBBRRB"

    Returns: 24

  86. "RRBRBRRRBRRBRRBBRRRBBBRRRRBBBBRRBRBRBRBRBBRBRBRRBB"

    Returns: 24

  87. "BRRBRBBR"

    Returns: 4

  88. "RBB"

    Returns: 1

  89. "RBRBRBRBBBBRRRRRBBBBBRRRRBBBRRRBBRBRBRBRRRBBBRBRRB"

    Returns: 24

  90. "RRR"

    Returns: 1

  91. "RRBRBRRRRBRRBRBR"

    Returns: 7

  92. "RBBRRBBRRRRBBRBRBRBRBRRBBRBBRRBRBBRBRBRBRBRBRRRRRR"

    Returns: 25

  93. "RRRBBBRRRBBB"

    Returns: 5

  94. "RBRBRBBBBBBBBRRBBRBBBBRBRBBBRRBBBRRRRBRRBRRBBRRRRR"

    Returns: 24

  95. "RBRBBRRBRBRBRBBBBBBBRRRBRBRRRBBRBRBRBRBRBRBRBRBRBR"

    Returns: 24

  96. "RRRRBB"

    Returns: 3

  97. "RBRRBR"

    Returns: 3

  98. "RRRRRRRRBBBRRRBBBRRR"

    Returns: 9

  99. "RRRBBRBB"

    Returns: 4

  100. "RBRBBBRBBBBBRRRRRBRBRBBRBRBRRBRBRRRRRRBBBBBBBBRBR"

    Returns: 24

  101. "BRBRBBRBRB"

    Returns: 5

  102. "RRBBBB"

    Returns: 3

  103. "BRRRBBBRRRRBBBRRRBBRBRBRBRBBBBBRRRRBRBBRBRBRBRBRBR"

    Returns: 24

  104. "RBBBBRBBBRRBRRBRRRBBBBBBBBBBBBRRRRRRRBRBRBRRRBRBRB"

    Returns: 24

  105. "RBBBRRRBRBRBBRRRRBBBBRRRBBBRRRRRRBBBRRBBBBBRRR"

    Returns: 22

  106. "RRBRBRBRB"

    Returns: 4

  107. "RBRBRB"

    Returns: 2

  108. "BRRRBB"

    Returns: 2

  109. "RRBRBRRRRBRRBRBRBBBBBBBBBBBBBBBBRRRBRRR"

    Returns: 19

  110. "RBBRBRBBRRBBR"

    Returns: 6

  111. "RBRBRBBRBRBRBRBBRBRBRBRBBRBRBRBRRBRBBRRBRBRRBRBRBB"

    Returns: 25

  112. "BRBRBRBRBRBBRBRBRBRBBRBBBBBBBBRRRBRBRRBRBRRBBRBRBR"

    Returns: 24

  113. "RBRBBRBRBRRBRBBR"

    Returns: 8

  114. "BRBBRRRBRBBRRR"

    Returns: 7

  115. "RRBBBRRRBBRRRBRBRRBBRRRBBRBRRBRRBRRBBBRBRBBRBBRRBB"

    Returns: 24

  116. "BRBRBRBRBRBBRBRBRBRBBRBBBBBRRRRRRBRRBBRBRBR"

    Returns: 21

  117. "RRBRBRBBRBBRBRBBRBRBRRBBBRRBRBBRBRBRRBBBRRBRBBBBRB"

    Returns: 24

  118. "RBRBRBRRBBRBRRBBRBRBRBRBRRRRRBBRBBBRRBBBBRBRBBBRRR"

    Returns: 24

  119. "RRRRBBBBBRBRBRBRBBBBBRRRRBBBBRRRRRBRBBBRR"

    Returns: 20

  120. "RRBBRBRBRBRBRRRBBRRBRRBRBRBRRRRBBRRRBBBRRRBBBBRBR"

    Returns: 24

  121. "RRBRBRBRRBBBBBBRRRBRBBBBBBRBRBRBBBBBBBBRBRRRRBRBRR"

    Returns: 24

  122. "RBRBRBRBRBRBRBRBRBRBRBRRBRRBRBRBRRRBBRBRRBRBRBRBRB"

    Returns: 24

  123. "RRBBBBRBRBRBBBRRBBBRRBBBRRR"

    Returns: 13

  124. "RBRBRBRB"

    Returns: 3

  125. "RBRBRBRBRRRRRRRBBBBBBBRRRRRBBBB"

    Returns: 15

  126. "RRRRRBRRBBRBRBBBB"

    Returns: 8

  127. "RBRBRRBB"

    Returns: 3

  128. "RRRRRRRRRRRRRRRRRRRRRRRRRBBBBBBBBBBBBBBBBBBBBBBBBB"

    Returns: 24

  129. "RBRBRRBBBRRRRRBBBRRBRBRBBRBRBRBBBBBBRBRRBBRBBRBRBR"

    Returns: 24

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: