PalindromePermutations | Topcoder Archive

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

```
"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.
```
"xxxxy"
```
```
Returns: 0.2
```
```
"xxxx"
```
```
Returns: 1.0
```
This word only has one anagram: "xxxx". That is a palindrome.
```
"abcde"
```
```
Returns: 0.0
```
Regardless of how we rearrange the letters of "abcde", we will never get a palindrome.

"hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhff"

Returns: 0.025641025641025637

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.