Statistics

Problem Statement for "SPartition"

Problem Statement

You are given a string of even length. You want to color each of its letters red or blue so that the red subsequence equals the blue subsequence. Count the number of ways in which this can be done.

Formally, you are given a String s. Let n be its length. You may assume that n is even and that each character in s is either 'o' or 'x'. Your method must return the number of pairs of sequences (X, Y) that satisfy the following criteria:

  • X = (x[0], ..., x[n/2-1]) such that x[0] < x[1] < ... < x[n/2-1].
  • Y = (y[0], ..., y[n/2-1]) such that y[0] < y[1] < ... < y[n/2-1].
  • {x[0], ..., x[n/2-1], y[0], ..., y[n/2-1]} = {0,1,...,n-1}. That is, each of the values 0 through n-1 is present either in X or in Y.
  • For each k such that 0 <= k < n/2 we have s[x[k]] = s[y[k]].

Definition

Class:
SPartition
Method:
getCount
Parameters:
String
Returns:
long
Method signature:
long getCount(String s)
(be sure your method is public)

Notes

  • You may assume that the return value always fits into a long.

Constraints

  • s will contain between 2 and 40 characters, inclusive.
  • The number of characters in s will be even.
  • Each character of s will be either 'o' or 'x'.

Examples

  1. "oxox"

    Returns: 2

    There are two ways to choose the pair of sequences: (x[0], x[1]) = (0, 1), (y[0], y[1]) = (2, 3) (x[0], x[1]) = (2, 3), (y[0], y[1]) = (0, 1)

  2. "oooxxx"

    Returns: 0

    It is possible that there is no valid pair of sequences.

  3. "xoxxox"

    Returns: 4

    The four valid pairs of sequences look as follows: (x[0], x[1], x[2]) = (0, 1, 2), (y[0], y[1], y[2]) = (3, 4, 5) (x[0], x[1], x[2]) = (3, 4, 5), (y[0], y[1], y[2]) = (0, 1, 2) (x[0], x[1], x[2]) = (0, 1, 3), (y[0], y[1], y[2]) = (2, 4, 5) (x[0], x[1], x[2]) = (2, 4, 5), (y[0], y[1], y[2]) = (0, 1, 3)

  4. "xo"

    Returns: 0

  5. "ooooxoox"

    Returns: 8

  6. "ooxxoxox"

    Returns: 8

  7. "oo"

    Returns: 2

  8. "xx"

    Returns: 2

  9. "xo"

    Returns: 0

  10. "ox"

    Returns: 0

  11. "oxox"

    Returns: 2

  12. "xxxx"

    Returns: 6

  13. "oxxx"

    Returns: 0

  14. "oooooooooooooooooooooooooooooooooooooooo"

    Returns: 137846528820

  15. "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"

    Returns: 35345263800

  16. "oxxooooooooooooooooooooooooooooooooooooo"

    Returns: 0

  17. "oooooooooooooooooooooooooooooooooooooxxo"

    Returns: 0

  18. "ooxxooxxooxxooxxooxxooxxooxxooxxoooooxxo"

    Returns: 87420

  19. "xooooooooooooooooooxxoooooooooooooooooox"

    Returns: 4

  20. "xoooooooooooooooooooxooooooooooooooooooo"

    Returns: 2

  21. "oooooooooooooooooooxooooooooooooooooooox"

    Returns: 2

  22. "oxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxox"

    Returns: 695878

  23. "oxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxox"

    Returns: 0

  24. "ooxxooxxooxxooxxooxxooxxooxxooxxooxxooxx"

    Returns: 8013698

  25. "ooxxooxxooxxooxxooxxooxxooxxooxxooxxoo"

    Returns: 3526552

  26. "ooooxxoxoxooooxxoxoxooooxxoxoxooooxxoxox"

    Returns: 1339844

  27. "oooxoxoo"

    Returns: 12

  28. "oxoxoxox"

    Returns: 6

  29. "xoxoxoxo"

    Returns: 6

  30. "xooxoxoxoo"

    Returns: 4

  31. "oxooxooxox"

    Returns: 12

  32. "xxxooxxxoo"

    Returns: 2

  33. "xxoxoxoxoxoo"

    Returns: 34

  34. "xoxoxoxoxoxo"

    Returns: 22

  35. "oxoxooxxxoxo"

    Returns: 24

  36. "xo"

    Returns: 0

  37. "oxxxoxxxxo"

    Returns: 0

  38. "xoxxxooxxxxooxooxoxx"

    Returns: 0

  39. "xxoxxxxxoxoxxxxoxxxxxxxxxxxxxo"

    Returns: 0

  40. "oxxxooxoooxoxxxoxxxoxxxooxxxxxxxoxoxxoxx"

    Returns: 0

  41. "oxox"

    Returns: 2

  42. "ooxoxoxoxxxo"

    Returns: 2

  43. "oxooxxoxooxxxoxxxxxo"

    Returns: 2

  44. "xoooooxoxoxoxoxooooxxoooxxoo"

    Returns: 6

  45. "xxooxoxxooxoxxooxxoxoxxxooxxoxxoxoxxooxo"

    Returns: 848600

  46. "xoxooxoxoxoxxxooxoxxooxoxxooxoxoxoxxoxoo"

    Returns: 409014

  47. "xxooooxoxoxxoxoxooxxooxoxooxooxoxxooxxxx"

    Returns: 2239122

  48. "xxoxooxxoxoxoxooxxooxoxxoxooxxxooxoxxxox"

    Returns: 427276

  49. "ooxoxxoxoxooxxoxooxxoooxoxooxoxooxoxooxx"

    Returns: 796766

  50. "xoxoxoxoxoxoxoxoxoxoxxooxxooxxoxoxooxx"

    Returns: 406884

  51. "xoxxoxoxoxoxxoxooxoxxoxoxooxxooxoxoxooxo"

    Returns: 265010

  52. "oxxoxxxxxxxxooooooxxooxx"

    Returns: 21280

  53. "xxxxooxooxoxoxooxxxxxoxxxoxxoxox"

    Returns: 43652

  54. "xxxooxoooxxxoxoxoxoxoxxxoxxoxooxoxxxoxoo"

    Returns: 26350

  55. "xxxxxxxxxxxxxxoxxoxxxxxx"

    Returns: 223080

  56. "xxxxoxxxxoxxxoxoxxxxxooxxxoxxxxxxxxxxoxx"

    Returns: 9720

  57. "xxxxxxxxxxxxxxxxxxxxxxxx"

    Returns: 2704156

  58. "xxxxxxxxxxxxxoxxxoxoxxxxxxoxxxxx"

    Returns: 1666236

  59. "xxoxxxxxxxxxoxxxxxxxxxxxxxxxxxxxxxxxxxxx"

    Returns: 626159820

  60. "xxxxxxoo"

    Returns: 40

  61. "xxxxxxxxxxxxxxoo"

    Returns: 6864

  62. "xxxxxxxxxxxxxxxxxxxxxxxx"

    Returns: 2704156

  63. "ooooooxxoooooooooooooooooooooooo"

    Returns: 108166240

  64. "ooooooxxxxxxxxxooxxxxxooxxxxxxxxoooooooo"

    Returns: 188176800

  65. "ooooooxx"

    Returns: 40

  66. "xxxxxxxxxxxxxxxx"

    Returns: 12870

  67. "xxxxxxxxoxxooxoxxxooxoox"

    Returns: 2032

  68. "xxoxoxxxxxxxxxxxxxxxoxxoxxxoxooo"

    Returns: 1651104

  69. "ooxooooxoxxoxxoooxoxoxoxxxxxxxxxxxxxoooo"

    Returns: 2471040

  70. "xxxoxxxooxoxxxxxxxxxxxxxxxxxxxxxxxxxxoxo"

    Returns: 120349800

  71. "oxoxoooooooooxoxoooooooooooxoooxooxxxxoo"

    Returns: 26247120

  72. "oooxooxooooxxoxxooxooooxoooooxooooxooooo"

    Returns: 1453864

  73. "xoxoooooooooooooooooooxxxxooooxooxxxoxox"

    Returns: 53461668

  74. "oxxxoxxxoxooxxoxoxoxoxxooxxxoxoxooxoxxoo"

    Returns: 64168

  75. "xoxxoxxoxxxoxoxoxoxxoxooxoxooooxoxxxooxx"

    Returns: 785136

  76. "xoxxxoxoxxoxoxoxoxxoxoxoxooxxoooxxoxoxox"

    Returns: 238704

  77. "oxoxoxxoxoxoooxxxoxoxooxxoxoxoxoxooxoxxo"

    Returns: 34800

  78. "xxxxooxoooxooxooxoxoxoxoxoooxxooooxxxxxx"

    Returns: 4363154

  79. "oxoxxxxxoxxoxxoxoxoxoxoxoxxxoxoxooxxoooo"

    Returns: 1871746

  80. "xxxxxxooxxxoxoxooxoxooxxooxooxoxooxxoxox"

    Returns: 1720566

  81. "xxxxooooooooxooooxxxooxxxxoxooxxoooxoooo"

    Returns: 7499712

  82. "xxxxooooxxxxooxxxxxxxxxxxxxxxxxxxoooxooo"

    Returns: 85861152

  83. "ooooooxxxxooooxoxoxxooxxxxoooooxxoxooxxx"

    Returns: 1398142

  84. "oooooxooooooooxoooxxxxxxxxxxxxxxoooooxox"

    Returns: 7687680

  85. "oxxoooxoxoxoxoxoxxxoxxoooxoxxoxxxooxxo"

    Returns: 5664

  86. "xxxooxoxoxooxoxxoxxoxxoooxooxoooooxoxx"

    Returns: 35808

  87. "xooxoxooxooxoxooxoxoxoxoxoxoxoxooxoxxx"

    Returns: 194350

  88. "xoxxxooxxoxxxxooxxooxoxxoxooxooxxoxxox"

    Returns: 88960

  89. "ooxxxoxooooooooooooooxoooxooxxooxxxoox"

    Returns: 2326896

  90. "ooxxxxxxooxxxxxxooooooooxxxoooxxxxxoxx"

    Returns: 5394480

  91. "ooxxooooooxxxxxxxooxxxooooooxxxxxoxoxx"

    Returns: 2016000

  92. "ooxxxxooxxxxxxxxxxxxxoxxoxxoxxxoooooxx"

    Returns: 3618160

  93. "ooxxooooooooooooooooooooooooooooooooxxxx"

    Returns: 14425929360

  94. "oooxxxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxox"

    Returns: 81930

  95. "xxoxxooxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxox"

    Returns: 0

  96. "xxoxoooxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxox"

    Returns: 359342

  97. "xoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxooooo"

    Returns: 1554752

  98. "ooxxoooxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxxx"

    Returns: 1477404

  99. "ooooxooxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxxo"

    Returns: 477402

  100. "xxxxoooxxoxxoxoxoxoxoxoxoxoxoxoxoxoxoxxo"

    Returns: 181966

  101. "ooooooooooooooooooooooooooooooooooooooxx"

    Returns: 70690527600

  102. "xxxxxxxxxxxxxxxxxxxxoooooooooooooooooooo"

    Returns: 34134779536

  103. "ooooooooooooooooooooooooooooooooooxxxxxx"

    Returns: 46672124400

  104. "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"

    Returns: 137846528820

  105. "xoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxo"

    Returns: 695878

  106. "ooooooooooooooooooooxxxxxxxxxxxxxxxxxxxx"

    Returns: 34134779536

  107. "ooooooooooooooooxxoooooooooooooooooooooo"

    Returns: 18157819680

  108. "oxoooxoooooxoooxoooooooooooxooxooooo"

    Returns: 5682996

  109. "oxoxoxoxoxox"

    Returns: 22

  110. "ooxxxxooxxoooxxoxoxoxoxxxooooooooooooooo"

    Returns: 1711710

  111. "xxxxoxxoxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"

    Returns: 11597315760

  112. "ooooooooooooooooooooxxoooooooooooooooooo"

    Returns: 17965673440

  113. "xxxooxxxoooxoxooxooxxoooooxxoxxoxxoxooxx"

    Returns: 71496

  114. "xxooxxxxxxxxoxxxxxoxxxxxxxxxxxxxxxxxxxxx"

    Returns: 1826966204

  115. "xoxxxxxoxoxxxxxxxoxxxxoxoxoxoxoxoxxxxxxx"

    Returns: 2209704

  116. "ooxxoxoxooxxoxoxooxxoxoxooxxoxoxooxxoxox"

    Returns: 932162

  117. "ooxoxooxooxoxoxooooxxxxooxxoxoxoxoxooxxo"

    Returns: 17336

  118. "ooooooooooooooooooooooooooooooooooooooox"

    Returns: 0

  119. "ooxxooooooooooooxoooxooooooooooooooooooo"

    Returns: 2314751760

  120. "xxxoox"

    Returns: 0

  121. "oxooxxoxxxxxoooxxoxooxoooxxoooxxoxooxxox"

    Returns: 210424

  122. "oxoxoxoxoxoxxxxxoxoxoxoooooxoxoxoxoxoxox"

    Returns: 52800

  123. "xxxxxxxxxxooooooooxoxxooxxxxxoxxoxxooxoo"

    Returns: 0

  124. "xoxooxxooooooooooxxooxxoxxxxoooxoxxxxxxx"

    Returns: 240

  125. "ooooxoxoxoxxxooxxoxoxoxoxoxxxxxxoooo"

    Returns: 812220

  126. "xxxxxxoooooooooooooooooooooooooooooooooo"

    Returns: 46672124400

  127. "ooooxxxxooooxxxxooooxxxxooooxxxxooooxxxx"

    Returns: 70297536

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: