PROBLEM LINKS
DIFFICULTY
SIMPLE
PREREQUISITES
Simple Math
PROBLEM
You are given a string of length N. Each character of the string is either a lowercase letter (‘a’ - ‘z’) or a question mark (‘?’). Count the number of ways to replace each question mark with a lowercase letter in such a way that the resulting string is a palindrome.
QUICK EXPLANATION
Consider the pairs of characters in the string that must be equal for the string to be a palindrome. First, the answer is 1. For each such pair, check the corresponding characters. If both characters are question marks, multiply the answer by 26. If exactly one of them is a question mark, or if both characters are equal lowercase letters, do nothing. If both characters are lowercase letters but they are not equal, set the answer to 0. For odd N, if the middle character is a question mark, also multiply the answer by 26.
EXPLANATION
In a palindrome of length N, the i-th character must be equal to the (N-i-1)th character (all indices are 0-based). For even N, there must be exactly N/2 pairs of equal characters: characters at positions 0 and N-1, positions 1 and N-2, …, positions N/2 - 1 and N/2. For odd N, there must be exactly (N-1)/2 pairs of equals characters: characters at positions 0 and N-1, positions 1 and N-2, …, positions (N-3)/2 and (N+1)/2.
For example, consider N=6. There must be exactly 3 pairs of equal characters: characters at positions 0 and 5, positions 1 and 4, positions 2 and 3. This ASCII art may illustrate better:
+---+---+---+---+---+---+ | 0 | 1 | 2 | 3 | 4 | 5 | +---+---+---+---+---+---+ | | | | | | | | +---+ | | | +-----------+ | +-------------------+
Another example, consider N=9. There must be exactly 4 pairs of equal characters: characters at positions 0 and 8, positions 1 and 7, positions 2 and 6, positions 3 and 5. Note that the middle character at position 4 is not included in any pairs.
+---+---+---+---+---+---+---+---+---+ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | +---+---+---+---+---+---+---+---+---+ | | | | | | | | | | | +-------+ | | | | | +---------------+ | | | +-----------------------+ | +-------------------------------+
Now, we want to count the number ways to replace the question marks in such a way that the resulting string is a palindrome. We can rephrase the problem into: count the number of ways to replace the question marks in such a way that each pair of characters as described above has equal letters. Note that each pair is independent. Therefore, for each pair, we can count the number of ways to make the pair have equal letters, and multiply them all to get the total number of ways.
Consider each pair. There are 4 cases:
- Both characters are question marks. We can replace one of them with any of the 26 lowercase letters. Since both letter must be equal, the other one must be also replaced with the same letter. The number of ways is 26.
- Exactly one of the characters is a question mark. We do not have other options besides replacing the question mark with the same letter as the other character. The number of ways is 1.
- Both characters are lowercase letters, and they are equal. This pair has already satisfied the requirement. The number of ways is 1 (i.e., do nothing).
- Both characters are lowercase letters, but they are not equal. Obviously, we cannot replace anything to make this pair have equal letters. The number of ways is 0.
There is a special case when N is odd. The middle character (i.e., the character at position (N+1)/2) is not included in any pairs. If the middle character is a question mark, we can replace it with any characters. Therefore, multiply the answer also by 26 if the middle character is a question mark.
The time complexity of this solution is O(N).
Do not forget to perform all calculations modulo 10,000,009.
SETTER’S SOLUTION
Can be found here
TESTER’S SOLUTION
Can be found here