Statistics

Problem Statement for "LeftOrRight"

Problem Statement

The Very Heterogeneous State of Feudalia's army is designing a new spy robot. Currently, the robot can only accept two commands: L and R. L moves the robot one unit of distance to the left, and R moves the robot one unit to the right. A program for the robot is a sequence of commands. For a given program, its reach is the distance between the starting point and the farthest point visited during the execution of the program. For example, the reach of the program "LLLR" is 3, because after the first three steps we reach a location 3 units away from the starting point.

Unfortunately, Feudalia is world famous for the ineptitude of its public officials. Some coffee was spilled all over the program before it could be installed to the robot. Therefore, some of the commands may now be illegible. Your task is to repair the program by replacing each illegible command with an L or an R. If there are multiple ways to repair the program, you have to pick one that maximizes its reach.

You are given a String program which describes the program in its current state. The i-th character in program represents the i-th command that is executed and will be 'L', 'R' or '?' (quotes for clarity). 'L' represents a legible move left, 'R' a legible move right and '?' a command that is illegible so you can choose 'L' or 'R' in its place. Return the largest reach a repaired program can have.

Definition

Class:
LeftOrRight
Method:
maxDistance
Parameters:
String
Returns:
int
Method signature:
int maxDistance(String program)
(be sure your method is public)

Constraints

  • program will contain between 1 and 50 characters, inclusive.
  • Each character of program will be 'L', 'R' or '?' (quotes for clarity).

Examples

  1. "LLLRLRRR"

    Returns: 3

    All commands are legible. The reach of this program is 3: both after three steps and after five steps we are 3 units to the left of the starting location.

  2. "R???L"

    Returns: 4

    We can replace all of the question marks with a right command.

  3. "??????"

    Returns: 6

  4. "LL???RRRRRRR???"

    Returns: 11

  5. "L?L?"

    Returns: 4

  6. "?"

    Returns: 1

  7. "L"

    Returns: 1

  8. "R"

    Returns: 1

  9. "??????????????????????????????????????????????????"

    Returns: 50

  10. "R?LRRRLLRLRLLLR??L??RRRLRL??L?RLR"

    Returns: 9

  11. "L??RL?LR?LRL?RLLL?L?L??RLR?R"

    Returns: 15

  12. "?LR???R?R?LLLLLRLR?RR?????LL??RR?R?LR??RL??LL?"

    Returns: 22

  13. "??R"

    Returns: 3

  14. "?RLRL?LL???LR?R?L?RRRL?????R?LRLR"

    Returns: 15

  15. "??RL?RLLL???L???L?R?LLLLRL??LRRLRRRL"

    Returns: 21

  16. "R?"

    Returns: 2

  17. "LRRLRRL???R?RL??L?LR?R??R??R?R"

    Returns: 18

  18. "?L??LLLR???LLLR?"

    Returns: 12

  19. "LRLRRRLRRLL?RRR?L??L?R???L?R?RLL"

    Returns: 14

  20. "LL???LRRLLLL??LLLL??RL?????R??L?LR?RLR?L?RL?LR"

    Returns: 29

  21. "RLLLLR?RL?LR?LRRL???LR??RL"

    Returns: 10

  22. "LRLR????RR?L?LL?R?R?LL?LR?R??RL?RLR?RL?LRR???RRLL"

    Returns: 23

  23. "?L"

    Returns: 2

  24. "R?L?R??L?R??LR??L??LLL?LL??LRL?R?LL?"

    Returns: 24

  25. "?RR?RLL?RRR???RL?R??RL?LR????"

    Returns: 19

  26. "?LR??LR?LL??RLRL??L?LLLR?L?RRRL?RRL"

    Returns: 17

  27. "LRL?RLRL?RL?LR?????LR?LR?LL"

    Returns: 13

  28. "RLRRLL??R?RL?R?RL?LRLLL?RLRLL?"

    Returns: 10

  29. "?LL??LLRRLLLLRRLL?L?RL?RLLLLRRR?L"

    Returns: 16

  30. "?LRR?RRLLRLR?RRRLRRR?R??RR???L"

    Returns: 19

  31. "????R?RRLLRL?LR?RRR?LRRR?RRLR??LR??LLL"

    Returns: 21

  32. "R???L?????RLL?LLRL"

    Returns: 12

  33. "???L?LRRR?R???RR???LL?R?RLR???L?R??L?LR?LR?RRRRRL"

    Returns: 30

  34. "RRL????LLLL???RL?R?R?R"

    Returns: 11

  35. "RRRL??R?R?L?RRL??RL?R?LR???R???LRLL?"

    Returns: 21

  36. "???RR?LRLRLLRR?R??L?LRL?LLR?RLLL?L?LL??LL?"

    Returns: 22

  37. "L?RRR"

    Returns: 3

  38. "LL?RR?RLR?LLRLLL??RLR?RR????"

    Returns: 10

  39. "RRRLR???RRLR?L???LR"

    Returns: 11

  40. "?RLLLLLRRLLLR??L?RL?RL?RLR?LRLRRLL?LR?R"

    Returns: 14

  41. "??RL??RRLRL?L?RRL?LRRRR?LR??LR????L??R?RLRLL??LR"

    Returns: 22

  42. "L?LL?R?RLL??LRL?R?LL?RLL?L????LR"

    Returns: 21

  43. "R??R?R?L??L??LRR?"

    Returns: 11

  44. "??LRL?RLRL?LR?LRRRL?RRLL"

    Returns: 8

  45. "LLR?RRL?R?RL?LLRL?L?LL?R?LR??"

    Returns: 13

  46. "RLLRLRLLL?RL??R??R?R?RRL???RLL?"

    Returns: 12

  47. "?RRRLR???L?RL?LRRR?RRRRRL?LL"

    Returns: 16

  48. "?RL????"

    Returns: 5

  49. "L?RLRRLRL?L"

    Returns: 3

  50. "LRLL?RL?LRR??"

    Returns: 5

  51. "L?LLLLLLRR?RLL?R?R?LRLLRRL??LRR??L???L"

    Returns: 18

  52. "RRLRL?RRLLR?LR?L?RLRR?L???LLLLL?L??LRLL?"

    Returns: 18

  53. "?LL????R"

    Returns: 7

  54. "??LL??"

    Returns: 6

  55. "LR?LR??R??LLL"

    Returns: 7

  56. "RLLLRL?L?LLL?L???R?LR?R?LRRR??LLLRL?LRLRR?LRLRL???"

    Returns: 22

  57. "R??LLL?R?L"

    Returns: 6

  58. "R???R?R?R?RLLLLL?L?LRR??L???L????RRLL?RR?LRLL"

    Returns: 21

  59. "LLR??LLR???R?L?L"

    Returns: 10

  60. "?R???????R?L???L?????R?L???R?R?L???????????R??????"

    Returns: 42

  61. "????L??LR??????R?R?R?????R?????????L????R???R"

    Returns: 39

  62. "?R??L??L??????L???L???????L?????L????R??L?????R?"

    Returns: 42

  63. "?????R??????L???R???????LRL?L??L?L?RL??R??????R?"

    Returns: 36

  64. "??????L??????R?RLLR?????R?????L?????R?RL?"

    Returns: 31

  65. "R???L?RR?R???????RR????????????R?L??????LR???"

    Returns: 39

  66. "???L??R????L???????RR???????L????????????R?"

    Returns: 37

  67. "L?L?R???R????????L?L????????????????????????"

    Returns: 40

  68. "L??????L????????L?????L???R?L?L??L??????RL???"

    Returns: 41

  69. "RR?L????RL???L??????LL???????????????????RL?????"

    Returns: 40

  70. "LRRLRLRRLRRRRLRLLRRRLRLRRLLLRRRLLRRLRRRR"

    Returns: 10

  71. "RRLLLLLRLRRLLRLLRRLLLLRRRRLLRRLLRLRRRLLRLLRRRRL"

    Returns: 6

  72. "LLLRLLRLRLLRLRLLRRLRRRLRRLLRRLLRRRRLLRRRLLRRL"

    Returns: 6

  73. "RLLLRRRRRLLLLLLLRRRRLLLLRLRRRRLLRLLRRRRRLLRRLRRLL"

    Returns: 4

  74. "RLLLLRLLRLRRRRLLRLLLRRLLRRLRRRLLLLRRLRRLLRLRLLRLRR"

    Returns: 4

  75. "RRLRRRLLRRLLLLRLLRRRLRRLLLRLRLLRRLLRRLRLLLRLR"

    Returns: 4

  76. "LRRRLLRRLLLRLLRRLRRLLLRRLRLRRLLRLLRRLRLLLRLLL"

    Returns: 5

  77. "RRLLRLLLRRLLLLRLRLRRRLLLRRLLRRRRLLRRRLLLLLLRLR"

    Returns: 5

  78. "LLLLLRRLLLLRLRRRLLLRRRLRLRRRRRLRLLLLRLLRRLRLRRLRRL"

    Returns: 7

  79. "LLLRRRLRRRLRLLRLLRRLLRRLLLLLRRLLRLRLRRRRRRRLR"

    Returns: 4

  80. "?LLRLLL?LLLLLLLR?LLRLRLLRRLRRRRRR?L?LLLLRRLLRRR"

    Returns: 16

  81. "LLRRRLLLRRLL?LLLRLRLRR?RRLRRRLLLL?LRLLLLL?LLLR"

    Returns: 15

  82. "LLLRLLLLLLLLRRRLLRLLLR??RLLLRRLRRRLRR?LLRLLRLLLLR?"

    Returns: 16

  83. "LRLLRRRRLRLRRLLLRLRRRL?LL?RLLRRLLLLLRLLL?LRRLLR"

    Returns: 10

  84. "LLLLLRRRRLRRRRLRLRRRL?LRLRLLRLLLRLRLLRL?RRLRRLRRR"

    Returns: 5

  85. "L?RLRL??RRRRLLLRLLRRRRLLRRLRRRRRRLRRLLRRLLRLRRR"

    Returns: 13

  86. "R?RRLRRRRRLRRRLLRLRRRLRRRRRRRLRRLLRLRRLRLLRLR"

    Returns: 18

  87. "LLLLRRRRLRLRLRLRLLRRLLLLLLLRLLL?RRRRRLRLRLL?LRLLRL"

    Returns: 10

  88. "LRLRLRRR?RLRLLRRRLRRLLRLRLRLLRRLRLRLRRRRR?LRR"

    Returns: 11

  89. "RLRLRRL?LLRRLRLLRRL?RLRRRRRRLL?RLRLRRLLRLRLLRLR"

    Returns: 9

  90. "RRLL?"

    Returns: 2

  91. "?LL?RRR"

    Returns: 4

  92. "L??????L????R??R??RR????R?R???R?RR?LL?L???????R?"

    Returns: 38

  93. "RRRR????LLL"

    Returns: 8

  94. "L?R?L?R?L?R?L?R?L?R?L?R?L?R?L?R?L?R?L?R?L?R?L?R?L?"

    Returns: 26

  95. "????????????????????????????????????????????????LL"

    Returns: 50

  96. "LLRR??R"

    Returns: 3

  97. "RRR???LLL"

    Returns: 6

  98. "RL??RL"

    Returns: 3

  99. "R?????????????L????????L???????????????????????L"

    Returns: 46

  100. "L?L?L?L?L?L?L?L?L?L?L?L?L?L?L?L?L?L?L?L?L?L?L?L?L?"

    Returns: 50

  101. "LLR?"

    Returns: 2

  102. "LLLLLRR?"

    Returns: 5

  103. "LR??????"

    Returns: 6

  104. "L??RR"

    Returns: 3

  105. "LLRRLLRRR"

    Returns: 2

  106. "RL???"

    Returns: 3

  107. "LRLRLRLLLL???RRRRR"

    Returns: 7

  108. "L?R??"

    Returns: 3

  109. "LL?RRR"

    Returns: 3

  110. "RR???????????????????????????????????LLL"

    Returns: 37

  111. "?LL?R?R"

    Returns: 4

  112. "L?R?LR"

    Returns: 3

  113. "RRLLL"

    Returns: 2

  114. "RR??LL??LL??R?R"

    Returns: 8

  115. "LRR??RRRLLLLLLL"

    Returns: 6

  116. "R?LL?R"

    Returns: 3

  117. "LL?RR"

    Returns: 3

  118. "LLLR??RRR"

    Returns: 4

  119. "L???RR?L"

    Returns: 5

  120. "L??R"

    Returns: 3

  121. "L?RL?RL?RL?RL?RL?RL?R"

    Returns: 8

  122. "??????????????????????????????????????????????L???"

    Returns: 50

  123. "LRR?LLLLLLLL"

    Returns: 8

  124. "?LLRR"

    Returns: 3

  125. "LR?"

    Returns: 1

  126. "LLLRRR????"

    Returns: 4

  127. "LL?RRR??"

    Returns: 4

  128. "L???R"

    Returns: 4

  129. "RRR?"

    Returns: 4

  130. "?L?R?L?R?L?R?L?R?L?R?L?R?L?R?L?R?L?R?L?R?L?R?L?R?L"

    Returns: 26

  131. "L?L?RR"

    Returns: 4

  132. "L?R?"

    Returns: 2

  133. "???R??L"

    Returns: 6

  134. "?LR"

    Returns: 2

  135. "LL???RRR"

    Returns: 5

  136. "RRRRRLL??"

    Returns: 5

  137. "LRR"

    Returns: 1

  138. "R?L?"

    Returns: 2

  139. "LL???RRR???R?RR???L"

    Returns: 14

  140. "LL?RLRR"

    Returns: 3

  141. "L?R"

    Returns: 2

  142. "??LL??RR"

    Returns: 6

  143. "RRRRLL?"

    Returns: 4

  144. "LLRR??"

    Returns: 2

  145. "LLLLLLLLLLLLLLLRRRLLLLLLLLLL"

    Returns: 22

  146. "RRLLLL?LRRR"

    Returns: 4

  147. "RRRRRLL?"

    Returns: 5

  148. "?L?R?L?R?RLR?R?R?L?R?LLL?L?RLRL?RL?L?L?R?L?R?L?R?L"

    Returns: 24

  149. "LR?RL"

    Returns: 2

  150. "LL??RR"

    Returns: 4

  151. "RRL"

    Returns: 2

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: