PalindromePermutations
SRM 625 · 2013-12-22 · by vexorian
SRM 625 · 2013-12-22 · by vexorian · Math
Problem Statement
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 aString word. We will choose one of its anagrams uniformly at random. Return the probability that the chosen anagram will be a palindrome.
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
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
0)
"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.
1)
"xxxxy" Returns: 0.2
2)
"xxxx" Returns: 1.0
This word only has one anagram: "xxxx". That is a palindrome.
3)
"abcde" Returns: 0.0
Regardless of how we rearrange the letters of "abcde", we will never get a palindrome.
4)
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" Returns: 1.0
Submissions are judged against all 198 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class PalindromePermutations with a public method double palindromeProbability(string word) · 198 test cases · 2 s / 256 MB per case