Statistics

Problem Statement for "PalindromePermutations"

Problem Statement

A palindrome is a word that reads the same forwards and backwards. For example, "a", "abba", and "zzz" are palindromes, while "ab" and "xxxyx" are not.

The anagram of a string S is any string we can obtain from S by rearranging its letters. For example, the string "haha" has exactly six anagrams: "aahh", "ahah", "ahha", "haah", "haha", and "hhaa".

We are given a String word. We will choose one of its anagrams uniformly at random. Return the probability that the chosen anagram will be a palindrome.

Definition

Class:
PalindromePermutations
Method:
palindromeProbability
Parameters:
String
Returns:
double
Method signature:
double palindromeProbability(String word)
(be sure your method is public)

Notes

  • The returned value must have an absolute or a relative error of less than 1e-9.

Constraints

  • word will contain between 1 and 50 characters, inclusive.
  • Each character of word will be a lowercase English letter ('a'-'z').

Examples

  1. "haha"

    Returns: 0.3333333333333333

    Each of the six anagrams of "haha" will be selected with probability 1/6. Two of them are palindromes: "ahha" and "haah". Hence, the probability of selecting a palindrome is 2/6.

  2. "xxxxy"

    Returns: 0.2

  3. "xxxx"

    Returns: 1.0

    This word only has one anagram: "xxxx". That is a palindrome.

  4. "abcde"

    Returns: 0.0

    Regardless of how we rearrange the letters of "abcde", we will never get a palindrome.

  5. "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"

    Returns: 1.0

  6. "aaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaa"

    Returns: 0.02040816326530612

  7. "aaaaaaaaaaaabaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaa"

    Returns: 0.02040816326530612

  8. "bbbbbbaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaa"

    Returns: 2.3562121533422868E-5

  9. "bbbbbbccaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaa"

    Returns: 5.746858910590944E-7

  10. "bbbbbbccaaaxxaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaa"

    Returns: 1.4735535668181907E-8

  11. "bbbbbbccaaaxxaaaaaaaaaabaaaaabaaaaaaaaaaaaaaaaaaaa"

    Returns: 1.4735535668181907E-8

  12. "bbbbbbccaaaxxaaaaaadaaabaaaaabaaaaaaaadaaaaaaaaaaa"

    Returns: 3.982577207616732E-10

  13. "aaaaabbbbbccccc"

    Returns: 0.0

  14. "hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhff"

    Returns: 0.025641025641025637

  15. "a"

    Returns: 1.0

  16. "vx"

    Returns: 0.0

  17. "vv"

    Returns: 1.0

  18. "abc"

    Returns: 0.0

  19. "abb"

    Returns: 0.3333333333333333

  20. "aaa"

    Returns: 1.0

  21. "abcd"

    Returns: 0.0

  22. "abcc"

    Returns: 0.0

  23. "aacc"

    Returns: 0.3333333333333333

  24. "aaac"

    Returns: 0.0

  25. "yyyy"

    Returns: 1.0

  26. "kolap"

    Returns: 0.0

  27. "kolpp"

    Returns: 0.0

  28. "koppp"

    Returns: 0.0

  29. "kpppp"

    Returns: 0.2

  30. "koopp"

    Returns: 0.06666666666666667

  31. "ooopp"

    Returns: 0.2

  32. "oooop"

    Returns: 0.2

  33. "abbccccddddddeeeeeeeeffffffffffgggggggggggg"

    Returns: 8.231619072008297E-17

  34. "aabbccccddddddeeeeeeeeffffffffffgggggggggggg"

    Returns: 8.231619072008298E-17

  35. "xxxxyyyyzzzzzzaaaaaa"

    Returns: 3.092882349848294E-6

  36. "abbcccc"

    Returns: 0.02857142857142857

  37. "abbccccdddddd"

    Returns: 3.33000333000333E-4

  38. "aabbccccdddddd"

    Returns: 3.33000333000333E-4

  39. "gwfqdjsbxaanyfsjvyyubaleoxcdsauduqnitbmbfgmfowgs"

    Returns: 0.0

  40. "jtxinudncsojfcdlpzknszjrehpma"

    Returns: 0.0

  41. "dktnyizrdauynahdunspqdqsmkjofqas"

    Returns: 0.0

  42. "gmwhogepeorswjdxazndbfswpf"

    Returns: 0.0

  43. "rsbrbjzqfnpgmjovv"

    Returns: 0.0

  44. "vqhkmgebpohbdepidenuhehydgauvmmaksn"

    Returns: 0.0

  45. "jnuiwetdrhirdydyfyfutubiq"

    Returns: 0.0

  46. "zxmsacprkokacolxpgxtdiguzxfecodxjx"

    Returns: 0.0

  47. "kbzwlrzkhnycroaxrpanjuubhe"

    Returns: 0.0

  48. "gnoimpsdfxt"

    Returns: 0.0

  49. "bqahxpqumhuuyuumxldxaabtknhu"

    Returns: 0.0

  50. "vlqlrcbzqbzhzpenquzqctgtubmxrhmhrugsmryjrg"

    Returns: 0.0

  51. "eateebjxmclawhplrwnfzsixurmgugfvl"

    Returns: 0.0

  52. "rtajybjgngnkhlifikqnqgvnkltcpxsgexzci"

    Returns: 0.0

  53. "nerldoiwtoyxmesrh"

    Returns: 0.0

  54. "rnrtgvswnqiqfjimjxsnyirnidazpnmcyafocqwtcaplq"

    Returns: 0.0

  55. "ybgvxbsxxjisnv"

    Returns: 0.0

  56. "ehlfanqhrlhhahnejs"

    Returns: 0.0

  57. "geswqxpfdefwjyz"

    Returns: 0.0

  58. "eptuwajxphkzlqkouzvllmnzfrtjpahp"

    Returns: 0.0

  59. "ihbvgdukjxrnuszzccf"

    Returns: 0.0

  60. "yioyedbsebqninslgohkwl"

    Returns: 0.0

  61. "nmbptbwxlhunatmxchejewiulldmpzprvpyjioydvbjwxbqdnc"

    Returns: 0.0

  62. "lhpsfdzzqoidqkkyysc"

    Returns: 0.0

  63. "qcwwainpxzfsdq"

    Returns: 0.0

  64. "yypnoetqeekyxyypxfmsbpfjywbpkvanuxplwr"

    Returns: 0.0

  65. "tndoxdgpzcuzfixelhsittshfbcfmgyh"

    Returns: 0.0

  66. "xjkvkmvofpuodiryucziheicggdbluixoyuipmzbkneviazg"

    Returns: 0.0

  67. "fdimocplazphyhjmtbscu"

    Returns: 0.0

  68. "xhgymycifwkpjem"

    Returns: 0.0

  69. "ylicletnzgegtopyltb"

    Returns: 0.0

  70. "fyihbwjxxdaicpbppszbkxfye"

    Returns: 0.0

  71. "hnkhccajsyuoiudbtcxplzkrmfgwbulmmxdefr"

    Returns: 0.0

  72. "tgbtgcfxuwuvqmbfffblpnipguijdyglfjxresrxsjcuckd"

    Returns: 0.0

  73. "krxzyqvgkgqyytzy"

    Returns: 0.0

  74. "jofxmjbwvebfymvjbazdg"

    Returns: 0.0

  75. "plnggeqpzroya"

    Returns: 0.0

  76. "olcvtlyzavxctvhzpsiljbbftqtxhyvuhhwymzidguhpkuuzt"

    Returns: 0.0

  77. "ttwqgyoketulxxgjcyyoabjochkpcpmfvncittoqhajfjustmf"

    Returns: 0.0

  78. "unoocibttwwfveyecbiiqsaiahgirolrahsozuydpwzeqhmtyu"

    Returns: 0.0

  79. "mlafgvpkfavjuxwvvtxylchnuwlynykmbtdnklhycxaijyatzq"

    Returns: 0.0

  80. "rfjgihdsmgbswpxqkeztfrjbrfgxsoyrkktxavjosulavhklf"

    Returns: 0.0

  81. "ttxxllyyffggyyiikkssxxffuuzzooo"

    Returns: 4.2209751582284217E-16

  82. "cceezzhhqqxxllttff"

    Returns: 2.901963686277412E-8

  83. "eettddeezzbbbbffjjllxxkkbbeeiivvxxvviilluuu"

    Returns: 9.696520978894836E-23

  84. "qqffuuiillxxjjj"

    Returns: 1.48000148000148E-6

  85. "zzggccqqbbggxxbbqqooyy"

    Returns: 1.963734825300504E-9

  86. "ggvvggrrwwhhuuzzqq"

    Returns: 8.705891058832235E-8

  87. "zznnuuuuwwxxrrggttzziinnooll"

    Returns: 1.2648855557491172E-13

  88. "uuwwyyoowwrrppvvoossqqppqquuu"

    Returns: 1.9627534485762166E-13

  89. "iimmaappddppffwwddwwiizzz"

    Returns: 3.0736719004703544E-11

  90. "rrxxttffnnrriikkk"

    Returns: 2.6117673176496706E-7

  91. "iimmjjbbrr"

    Returns: 0.0010582010582010583

  92. "tthhrrxxllii"

    Returns: 9.62000962000962E-5

  93. "rrzzuuaaeeiippeeiivvooeeffjjkk"

    Returns: 7.26945721694895E-15

  94. "mmcchhooddrraazzdduujjzzeehhwwaaffrrlll"

    Returns: 2.279328864772213E-21

  95. "oottoooojjaaxxiiaattttaaffyyqqwwqqxxtt"

    Returns: 2.5927365836783925E-17

  96. "qqhhnnhhxxnnddff"

    Returns: 4.44000444000444E-6

  97. "ppkkuubbkkssaarrkkmmffffoogguuyyrr"

    Returns: 6.395416906406698E-17

  98. "ppwwiiooggaammffooxxiibboorrvvhhh"

    Returns: 2.1318056354688997E-17

  99. "ffppnnllppwwddmmnn"

    Returns: 2.6117673176496706E-7

  100. "ggnnwwmmnnuuxxssppjjkkggnnbbbb"

    Returns: 2.1808371650846847E-14

  101. "vvzzwwvvbbffaauuwwzzzzddaaddkkmmkkxx"

    Returns: 1.6445357759331513E-17

  102. "hhiiggvvbbqqggggllvvggssddjjffqqvviinnooiibbbbdd"

    Returns: 2.674375368489513E-24

  103. "vvxxaattyyppeesssszzvvzzbbbb"

    Returns: 3.794656667247352E-13

  104. "ccppppoobbzzuuwwssrrccllzzddoonnffppttyyppyy"

    Returns: 1.5083477078280853E-23

  105. "jjllbbaavvmm"

    Returns: 9.62000962000962E-5

  106. "sszzwwkkyymmhhvvfff"

    Returns: 4.582047925701176E-9

  107. "eeggttllssyyooooqqddqqwww"

    Returns: 3.415191000522616E-12

  108. "ssppddfftteepptt"

    Returns: 4.44000444000444E-6

  109. "jjuubbttppggbbb"

    Returns: 7.4000074000074E-6

  110. "fftthhzzggssggppnnttcczzkkeee"

    Returns: 1.308502299050811E-14

  111. "kkttyytteehhccssgguullmmooffhhrrddbbccc"

    Returns: 4.220979379207801E-22

  112. "oorrmmuullbbqqeennffbbuuiikkhhssiivviii"

    Returns: 2.9546855654454606E-21

  113. "vvkkmmssqqeexxvvoohhmmrrllggssrraajjaaoohhh"

    Returns: 1.939304195778967E-23

  114. "mmiikknnqqbbaayyuuhhyyhheeoowwttppmmm"

    Returns: 1.6461819578910428E-20

  115. "vvmmvvvvzzuuvvppxxhhyyff"

    Returns: 3.3203245838414325E-10

  116. "ccggmmoovvvvwwvvooyyzzccjjddccooeettaaeekkppddmmm"

    Returns: 7.797012736121029E-27

  117. "qqffnnrrvvoorrbbnnddqqllqqwwkkhhffaabbnnzzhhkkzznn"

    Returns: 1.9648472095024996E-26

  118. "rrppffoobbjjiieeddeennrrffllkkqqggg"

    Returns: 3.6545239465181142E-19

  119. "zzyyssbbttkkiiffjjmmggnnhhllggrrvvbbb"

    Returns: 5.487273192970142E-21

  120. "kkggvvyyjjuuyymmqqssppddllnnqqyyoojjjjrrbbee"

    Returns: 1.1971013554191156E-24

  121. "xxllxxaaeezzqqbbllzzwwhhllyyggnnuuxxhhuu"

    Returns: 1.8994407206435107E-20

  122. "oolleehhssaajjddeeeeeexxyyyyiiccqqvvxxffqqffppp"

    Returns: 2.1395002947916104E-26

  123. "eewwxxiixxbbssiimmqq"

    Returns: 1.3746143777103529E-8

  124. "xxgguurrzzggssxxjjqqiiss"

    Returns: 8.53797750130654E-11

  125. "aarrzzooqqhhffjjbbssqqlljjcclleexxggffxx"

    Returns: 7.597762882574043E-22

  126. "vvqqssaappjjddyyvvrrvvwwkkggookkiiooiii"

    Returns: 6.331469068811702E-21

  127. "ooeeppllnnrrgguuiigglll"

    Returns: 1.4229962502177566E-10

  128. "ffuukksseemmssttffzziiyyrr"

    Returns: 1.1383970001742053E-12

  129. "kkppccrroojjvvccyyttyyggnnqqaaeeqqggppyynnqqddnnn"

    Returns: 1.0915817830569441E-26

  130. "ggxxhhwwllqqbbqqttffyyqqq"

    Returns: 1.3281298335365727E-11

  131. "ddzzvvhhxxnnjjddssnnddooyyiiccccbbvvssiiiiqqpplll"

    Returns: 9.356415283345237E-28

  132. "yynnppeehhcczzoowwrrggssssqqaakkeeiiffeeggttwwuuu"

    Returns: 2.0792033962989408E-29

  133. "ddeeyyjjwweeooyyjjqqvvgguukkbbeerruujjnnmmnnttaayy"

    Returns: 5.198008490747354E-28

  134. "mmccmmrrddkkjjwwyykkoopprrkkffssqqooggjjuuccggaavv"

    Returns: 1.8712830566690475E-28

  135. "ssmmuusssseewwaakkccssmmppllnnuubbiiyyuunnppnneecc"

    Returns: 3.274745349170833E-26

  136. "qqttooffffccppzziirrjjaabbccssssnnxxddooxxwwsssss"

    Returns: 1.3098981396683328E-27

  137. "sszzqqqqqqtteeppvvuuffffiimmzzqqffyyxxbbnnhhxxqqq"

    Returns: 2.401479922725277E-26

  138. "oonnqqzzxxaarrccbbhhkkbbllkkvvvvsskkoottwwkkqqkktt"

    Returns: 3.929694419004999E-27

  139. "yyaaooeeffbbkkbbkkiizzttyyffssqqccaarrttbbbbbbuuu"

    Returns: 1.1789083257014998E-26

  140. "vvssmmbbhhddllssccnneeqqvvmmrrxxmmttmmeeppmmiieee"

    Returns: 1.5282144962797214E-26

  141. "wwqqeeffkk"

    Returns: 0.0010582010582010583

  142. "zzbbkkssss"

    Returns: 0.0031746031746031746

  143. "tthhuuggg"

    Returns: 0.0031746031746031746

  144. "oowwllwww"

    Returns: 0.015873015873015872

  145. "ppeehhqqnn"

    Returns: 0.0010582010582010583

  146. "kkvvzznnn"

    Returns: 0.0031746031746031746

  147. "rruussmmgg"

    Returns: 0.0010582010582010583

  148. "vvkkrrppp"

    Returns: 0.0031746031746031746

  149. "vvllqqsss"

    Returns: 0.0031746031746031746

  150. "bbrrwwssaa"

    Returns: 0.0010582010582010583

  151. "bbccyynneerrppiiaabb"

    Returns: 4.582047925701176E-9

  152. "ssxxqqggggxxppxxhhh"

    Returns: 2.0619215665655295E-7

  153. "rrqqppppiieennrrddbb"

    Returns: 1.3746143777103529E-8

  154. "sszzppzzppiinnxxeeyy"

    Returns: 1.3746143777103529E-8

  155. "qqppuubbffooffzzsss"

    Returns: 1.3746143777103529E-8

  156. "ppddccxxppddbbddooo"

    Returns: 2.0619215665655295E-7

  157. "kkyykksszzmmyyaavvv"

    Returns: 4.123843133131059E-8

  158. "ddvvvvzzaabbiiccppvv"

    Returns: 2.2910239628505883E-8

  159. "ggttuuzzssffrrggeebb"

    Returns: 4.582047925701176E-9

  160. "vvnnqqssvvzzzzyyppss"

    Returns: 4.123843133131059E-8

  161. "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbb"

    Returns: 0.0013026487190620926

  162. "aabbccddeeffgghhiijjkkllmmnnooppqqrrssttuuvvwwxxyy"

    Returns: 1.7112785154723798E-32

  163. "aaaabbbbccccddddeeeeffffggiiigghhhh"

    Returns: 8.880493190039017E-17

  164. "xxxxyyy"

    Returns: 0.08571428571428572

  165. "xxyyy"

    Returns: 0.2

  166. "xxxxx"

    Returns: 1.0

  167. "ab"

    Returns: 0.0

  168. "aaabb"

    Returns: 0.2

  169. "abcdefghijklmnopqrstuvwxyabcdefghijklmnopqrstuvwxy"

    Returns: 1.7112785154723798E-32

  170. "aaaaa"

    Returns: 1.0

  171. "aaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbb"

    Returns: 4.2783688429366084E-8

  172. "aabbddd"

    Returns: 0.02857142857142857

  173. "xxxxxyy"

    Returns: 0.14285714285714285

  174. "eebeb"

    Returns: 0.2

  175. "aaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbb"

    Returns: 4.2783688429366084E-8

  176. "xxxaa"

    Returns: 0.2

  177. "aaaaaaabbcccc"

    Returns: 0.002331002331002331

  178. "aabcabcaa"

    Returns: 0.015873015873015872

  179. "cababcacabacaababcaacbabbccabcacabacabbbcaabababbb"

    Returns: 4.013422170271845E-12

  180. "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaass"

    Returns: 0.02040816326530612

  181. "xxyyyyy"

    Returns: 0.14285714285714285

  182. "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabb"

    Returns: 0.02040816326530612

  183. "cbcccbc"

    Returns: 0.14285714285714285

  184. "aaaaaaa"

    Returns: 1.0

  185. "aaaabbbbcc"

    Returns: 0.009523809523809525

  186. "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabb"

    Returns: 0.024390243902439025

  187. "aaaaabb"

    Returns: 0.14285714285714285

  188. "aaabbcc"

    Returns: 0.02857142857142857

  189. "aaaabbbb"

    Returns: 0.08571428571428572

  190. "aabbb"

    Returns: 0.2

  191. "eeddc"

    Returns: 0.06666666666666667

  192. "aaabbbb"

    Returns: 0.08571428571428572

  193. "aaaaaabbbbbbccccccddddddeeeeeeffffffgggggghhhhhhii"

    Returns: 4.38581966406808E-23

  194. "aaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbb"

    Returns: 4.2783688429366084E-8

  195. "baaab"

    Returns: 0.2

  196. "aaaaaabbbbbbccccccdddddd"

    Returns: 1.6008707814949762E-7

  197. "ssees"

    Returns: 0.2

  198. "gfg"

    Returns: 0.3333333333333333

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: