Statistics

Problem Statement for "TripleStrings"

Problem Statement

You have three strings A, B, C. Initially, A is equal to a String init, and B and C are empty. Each character of init is either lowercase 'o' or lowercase 'x'.

Your task in this problem is to transform A from init into goal by applying the following operations to the strings.

  1. If A is not an empty string, remove the leftmost character from A, and add it to the end of B.
  2. If A is not an empty string, remove the leftmost character from A, and add it to the end of C.
  3. If B is not an empty string, remove the leftmost character from B, and add it to the end of A.
  4. If C is not an empty string, remove the leftmost character from C, and add it to the end of A.

You can apply the operations in any order and each operation can be used an arbitrary number of times. Return the minimal number of operations required to finish the task. The constraints guarantee that this is always possible.

Definition

Class:
TripleStrings
Method:
getMinimumOperations
Parameters:
String, String
Returns:
int
Method signature:
int getMinimumOperations(String init, String goal)
(be sure your method is public)

Constraints

  • init will contain between 1 and 50 characters, inclusive.
  • init and goal will contain the same number of characters.
  • Each character of init and goal will be either lowercase 'o' or lowercase 'x'.
  • The number of 'o' characters in init will be equal to the number of 'o' characters in goal.

Examples

  1. "ooxxox"

    "xoxoxo"

    Returns: 6

    One of the optimal solutions is as follows: initial: A=ooxxox B= C= use operation 1: A=oxxox B=o C= use operation 2: A=xxox B=o C=o use operation 2: A=xox B=o C=ox use operation 4: A=xoxo B=o C=x use operation 4: A=xoxox B=o C= use operation 3: A=xoxoxo B= C=

  2. "oooxxoo"

    "oooxxoo"

    Returns: 0

    init and goal are the same, so no operation is required.

  3. "ox"

    "xo"

    Returns: 2

  4. "ooxxooxx"

    "xxoxoxoo"

    Returns: 12

  5. "oxxoxxoooxooooxxxoo"

    "oxooooxxxooooxoxxxo"

    Returns: 16

  6. "xxxoxoxxooxooxoxooo"

    "oxxooxxooxxoxoxooxo"

    Returns: 36

  7. "x"

    "x"

    Returns: 0

  8. "o"

    "o"

    Returns: 0

  9. "xx"

    "xx"

    Returns: 0

  10. "ox"

    "xo"

    Returns: 2

  11. "oo"

    "oo"

    Returns: 0

  12. "xxx"

    "xxx"

    Returns: 0

  13. "oox"

    "oox"

    Returns: 0

  14. "ooo"

    "ooo"

    Returns: 0

  15. "xxoxxox"

    "xxooxxx"

    Returns: 12

  16. "oxoooxo"

    "xxooooo"

    Returns: 14

  17. "oxxoxoo"

    "oxoxxoo"

    Returns: 12

  18. "oooooxoxxoxooo"

    "oxoxxooooooxoo"

    Returns: 26

  19. "xoxooooxxoxoxx"

    "xxoxooooxxxoox"

    Returns: 24

  20. "oxooooxxxoxxoo"

    "xxoxoxoooxooox"

    Returns: 28

  21. "ooooooxoxoxxxxooooooo"

    "ooooxooooxxoxoxooooxo"

    Returns: 34

  22. "xxxxxxxxxxoxxoxxxxxxx"

    "xxoxxxxxxxxxxxxxxxxxo"

    Returns: 22

  23. "xoooxoooooxxooooooooo"

    "oxoooooxooooxooooooox"

    Returns: 40

  24. "ooooxoxooooooooooooooooooooo"

    "oooooooooooooooooooooxoooxoo"

    Returns: 14

  25. "xxxxxxxxxxxxxxoxxxxxxxxoxxxx"

    "xxxxxxxxxxxxxxxxxxxxxxxxxoox"

    Returns: 48

  26. "oooxooxoxxoxooxxoxooxooxooox"

    "ooxxxooxoooxxxxoooxooxooooxo"

    Returns: 50

  27. "xxoxooxoxox"

    "xxxxxooooxo"

    Returns: 20

  28. "oooooooxxoo"

    "oxxoooooooo"

    Returns: 12

  29. "xxooxooxoxx"

    "ooxooxoxxxx"

    Returns: 4

  30. "ooxooxoxoxooxxxoxoxxxx"

    "oxxxxxooxxxooxoxoxoxoo"

    Returns: 34

  31. "xoooxxxxxxxxooxxooxooo"

    "xxooxxooxoooxxoxxxxoox"

    Returns: 20

  32. "oxxxxoxooxxxoxooooooxx"

    "xxxoxooxxxoxooooooxxxo"

    Returns: 4

  33. "xoxxoooooooxooxxooxxooooxxxoxxoxx"

    "xxxoxxoxxxoooxooxxoooxoxxooooooox"

    Returns: 48

  34. "oxxxxooxxoooxxxooxxxoxoxxxxooxoxo"

    "xxooxxxoxoxxxxooxoxoxxoooxxoxoxox"

    Returns: 26

  35. "ooxoxxoxxxxxooxooxooxoxxxxxoxoxox"

    "xoxxoxxxxxooxooxooxoxxxxxoxoxoxoo"

    Returns: 4

  36. "xoooxxxoooxoooxoxxoxxoooxxxxxxxxxxooooxxxxxo"

    "xxooooxxxxxoxoxxxxxxoxxxoooooxxooooxoxxoxxxo"

    Returns: 64

  37. "ooxxoxxxxoxoxooxoxoxooxxxxxxooxxxxxxoxxxoxoo"

    "xoxooxxxxxxooxxxxxxoxxxoxooxxxoxoxooooxoxoxx"

    Returns: 34

  38. "oxoxoxxxoxoxoooxxoxoxxxoxoxxooxooxxooooxxoox"

    "oxoxxxoxoxoooxxoxoxxxoxoxxooxooxxooooxxooxxo"

    Returns: 4

  39. "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"

    "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"

    Returns: 0

  40. "oooooooooooooooooooooooooooooooooooooooooooooooooo"

    "oooooooooooooooooooooooooooooooooooooooooooooooooo"

    Returns: 0

  41. "xxxxxxxxxoxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"

    "xxxxxxxxxxxxxxxxxoxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"

    Returns: 66

  42. "ooooooooooooooooooooooooooooooooooooooooooooooxooo"

    "ooxooooooooooooooooooooooooooooooooooooooooooooooo"

    Returns: 88

  43. "xxxxoxxxoxxoxxxoxxxxoxxxxxxxoxxoxxxxxxxxxxoxxxxxxo"

    "xxoxoxxxoxoxxxxxxoxxxxxxxxxxooxxxxxxxxxoxxxoxxxxxx"

    Returns: 94

  44. "xxxoxoxoxxxxxxxoxoxoooxxoxooxxxxooxxxxxoxxxxxxoxox"

    "xxxxxoooxxooxxoxxxoxxxxoxxxoxxxxxxooxooxxoxxoxxoxx"

    Returns: 98

  45. "oxxxoooxoxxxxoxxxxooxoxoxoxxooxooooxxoxxooxoxoxxox"

    "xxoxooooxooooxxooxooxxoxoxxxoxxxxxxoxooxxooxoxxxxo"

    Returns: 92

  46. "oxooxxoxooooxxxooooxxooxooxxoooooooxoxxoooooxxoxxx"

    "xxooooooxooxoooooxoooxooooxoxxxooxoxxoxoxxxxoxoxoo"

    Returns: 96

  47. "oooooxoxoooxxoooooooooxoooxoxoooxooxooxxooooxxoooo"

    "oooxooooooooooxoxxoxxooxooooxoooxoooooooxooxoooxxo"

    Returns: 94

  48. "xooooooooooooxoooooooooxooxoooooxooooooooooxoooooo"

    "oooooooxoxoxxooooooooxoooooooooooooooooxoooooooooo"

    Returns: 88

  49. "ooxxxxoxxxoxxoxxooooxoooxoooxxxxoxooxooxxoxooxooxx"

    "oxooxooxxooxxoooxooxxxooxxoxoooxxoxoxxxooxxxxxooxo"

    Returns: 82

  50. "ooxoxxoxooxoxxoxxoxooxxoxoxoxxooooxooooooxxxxxoxxx"

    "xooooooxxxxxoxxxooxoooxooxooxxxoooxxoxxxxxoxoxxooo"

    Returns: 68

  51. "oxxooxoxoxxxooxxoooxoxooooxxoxoxooxxxoxxxoxoxoxxxx"

    "xoxoxooxxxoxxxoxoxoxxxxoxoooooxxxooxoxoxxooxxoxoxo"

    Returns: 54

  52. "oooxooooxxxxxoxxxoxxooooooxoooxxoxxxxxxooxoxoxxoox"

    "ooooooxoooxxoxxxxxxooxoxoxxooxoxoxxxxooooxoxoxxxox"

    Returns: 40

  53. "oooxxxooxxoooxooxxxxooooxoxoxoxxxoxooxoxoxxxxxoxxo"

    "xooxxxxooooxoxoxoxxxoxooxoxoxxxxxoxxoxooxooxoxooox"

    Returns: 26

  54. "xoxxxxxoxoooooxoxxooooooxoxxoooxooxxxxxoxxoxoxoxxx"

    "xoxoooooxoxxooooooxoxxoooxooxxxxxoxxoxoxoxxxxoxxxx"

    Returns: 12

  55. "xoxoxooxooxxooxxxxxoxoxoooxxxooxoooxxooxxooxxxxxoo"

    "xoxooxooxxooxxxxxoxoxoooxxxooxoooxxooxxooxxxxxooox"

    Returns: 4

  56. "oxoooxxxoooxoooxoxxooxoxooxooxxxoxooxooooooxxxooox"

    "ooxxxoooxoooxoxxooxoxooxooxxxoxooxooooooxxxoooxxoo"

    Returns: 6

  57. "ooooooxxoxooxooxoxxxxoooxooxoxooooxooxooxxxoxooooo"

    "ooxxoxooxooxoxxxxoooxooxoxooooxooxooxxxoxooooooooo"

    Returns: 8

  58. "oooxxxxooxxxooxxxoooxoxoxoooxooooooxxxooxoxoooxxox"

    "xooooooooxoxooxooxoxooxoxooxxxxxxxxoxxooxoooxooxox"

    Returns: 98

  59. "xxoxxxooooxoooxxoooxxooxoxooxoxxxxoxxxoxooxoooooxx"

    "xxxoooxxxxooooxooxoxoxxooxooxxxoxxooxooooxxoxoxxoo"

    Returns: 96

  60. "xoxxxxxoxoooxooooxoxoxoxxxxooxoxxooooxxxoxxxxxxoxo"

    "oxoxxoxooooxxooxooxxxoxxxxoxxxxoooxoxxoxxxoxxxxooo"

    Returns: 94

  61. "xoxooxooxxooxxxxxoxoxoooxxxooxoooxxooxxooxxxxxooox"

    "xoxooxooxxooxxxxxoxoxoooxxxooxoooxxooxxooxxxxxooox"

    Returns: 0

  62. "xoxo"

    "xxoo"

    Returns: 8

  63. "ooxx"

    "oxox"

    Returns: 8

  64. "oxxox"

    "ooxxx"

    Returns: 10

  65. "oooxxxooxxoooxxxooxxoooxxxooxxoooxxxooxxoooxxxooxx"

    "oxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxox"

    Returns: 100

  66. "oxox"

    "ooxx"

    Returns: 8

  67. "oooooooooooooooooooooooooxxxxxxxxxxxxxxxxxxxxxxxxx"

    "ooooooooooooooooooooooooxoxxxxxxxxxxxxxxxxxxxxxxxx"

    Returns: 100

  68. "ooooooooooooooooooooooxoxxxxxxxxxxxxxxxxxxxxx"

    "oooooooooooooooooooooooxxxxxxxxxxxxxxxxxxxxxx"

    Returns: 90

  69. "ooooooooooooooooooooooooooooooooooooooooooooooooxx"

    "oxoxoooooooooooooooooooooooooooooooooooooooooooooo"

    Returns: 100

  70. "xxoo"

    "xoxo"

    Returns: 8

  71. "xxxooo"

    "xoxoxo"

    Returns: 12

  72. "xoxoxoxoxoxoxoxxxxxxxxxx"

    "xxxxxxxxxxxxxxxxxooooooo"

    Returns: 28

  73. "oooxxx"

    "oxoxox"

    Returns: 12

  74. "oxoxx"

    "ooxxx"

    Returns: 10

  75. "xxxxooxxoooxxxoxxxxoxoxooxxooxoxxoxooxxoxxoxo"

    "xxooooxxooxxxxxxxxoxooxxxoxxxoxooxoxoxoooxoxx"

    Returns: 90

  76. "ooxox"

    "oooxx"

    Returns: 10

  77. "xoooxooxxxxoxxoxoxoxoxxoxxxoxooxooxxoooxxooxxxooxo"

    "oxxooxoxoxxoxxooxoxxxoooxxxxoxoxxoxxxoooxoooooxxox"

    Returns: 98

  78. "oxoox"

    "oooxx"

    Returns: 10

  79. "ooooxoxo"

    "ooooxxoo"

    Returns: 14

  80. "xxxxxxxxxxxxxxxxxxxxxxxxxooooooooooooooooooooooooo"

    "xxxxxxxxxxxxxxxxxxxoxxxxxooooooooooxoooooooooooooo"

    Returns: 100

  81. "xoxox"

    "ooxxx"

    Returns: 10

  82. "xxooo"

    "xooxo"

    Returns: 10

  83. "xoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxo"

    "xxooxxooxoxxooxxooxxooxxooxxooxxooxxooxxooxxooxxoo"

    Returns: 100

  84. "oxoxoxox"

    "ooooxxxx"

    Returns: 16

  85. "xoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxo"

    "xxxxxxxxxxxxxxxxxxxxxxxxxooooooooooooooooooooooooo"

    Returns: 100

  86. "xoxxoxoxxooxxxxooxxoxxxoxxxxooooxoxxoxxoxooxoooxoo"

    "ooxoxxxoxoxxoxxoxoxxoooxxoxxxoxxxxooooxxxoxxxooooo"

    Returns: 96

  87. "oooxx"

    "oxoxo"

    Returns: 10

  88. "xxoxxoo"

    "xoxooxx"

    Returns: 14

  89. "xoxoxo"

    "xxxooo"

    Returns: 12

  90. "oxoxoxooxxxoxxxxxoxoxxxxoxo"

    "xxxxooooxxoxxxoxoxoxxxxooxx"

    Returns: 54

  91. "xxxxoooooo"

    "xoooxxooxo"

    Returns: 20

  92. "xooxo"

    "xxooo"

    Returns: 10

  93. "ooxxoo"

    "xoxooo"

    Returns: 12

  94. "ooxoxx"

    "oooxxx"

    Returns: 12

  95. "ooxxx"

    "oxxox"

    Returns: 10

  96. "xxooxx"

    "oxoxxx"

    Returns: 12

  97. "oxoxxx"

    "oxxoxx"

    Returns: 12

  98. "xxoxoo"

    "xxxooo"

    Returns: 12

  99. "oxxoo"

    "xoxoo"

    Returns: 10

  100. "oxxoox"

    "oooxxx"

    Returns: 12

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: