Count Palindrome Addition Choices
The D.E. Shaw Group● EasyFULLTIMEOAProblem statement
You are given a string inputStr. Choose either to add no letter or to add one of the 26 lowercase English letters.
Count the choices for which the resulting letters can be rearranged into a palindrome.
- Adding a particular letter counts as one choice, regardless of where it is inserted.
- Different palindromes made from the same letters do not count as different choices.
- Adding no letter is one separate choice.
Return the number of valid choices. The answer is between 0 and 27.
Function
countPalindromeAdditions(inputStr: String) → intExamples
Example 1
inputStr = "aabb"return = 27Adding no letter is valid, and adding any one of the 26 letters is also valid. These give 1 + 26 = 27 choices. Insertion positions and rearrangements do not add choices.
Example 2
inputStr = "abbb"return = 2Both a and b have odd counts. Adding a or b leaves exactly one odd count, so both choices work. Adding nothing leaves two odd counts and fails. The answer is 2.
Example 3
inputStr = "abc"return = 0There are three odd letter counts. Adding one letter leaves at least two odd counts, so no palindrome can be formed. The answer is 0.
Constraints
- For this exercise, assume
1 <= inputStr.length <= 10^5. inputStrcontains only lowercase English letters.