### PROBLEM LINK:

**Author:** Sunny Agarwal

**Testers:** Alex Gu and Pushkar Mishra

**Editorialist:** Prateek Gupta

**Russian Translator:** Vitalij Kozhukhivskij

**Vietnamese Translator:** Khanh Xuan Nguyen

**Mandarian Translator:** Gedi Zheng

**Contest Admin**: Praveen Dhinwa and Pushkar Mishra

### DIFFICULTY:

Easy Medium

### PREREQUISITES:

Hashing, Strings

### PROBLEM:

Given a string, output the number of positions where a letter can be inserted so that the resulting string is a palindrome.

### RECOMMENDED READING

Hashing Tutorial

Anti Hash Cases

### Naive Approach:

The naive approach is to try inserting all 26 lowercase characters at all N+1 positions and henceforth checking whether the final string is a palindrome or not every single time. So, this approach would result in \mathcal{O}(N*26) for each single positions. Checking for all positions will result in \mathcal{O}(26*N^2) complexity. This naive approach could be optimized a little to remove a constant factor of 26.

While we insert a character at position i, it should match the character at (N-i-1)^{th} position. So, it’s good enough to insert the same character which occupies (N-i-1)^{th} position, and then checking whether the string is palindrome or not. This will reduce the complexity to \mathcal{O}(N^2)

### An \mathcal{O}(N) solution:

The faster approach that exists is to optimize the naive approach. However, the logic is still the same.

What needs to be optimized is to check whether the string after insertion still remains a palindrome. This can be done without inserting the character at all kinds of positions and without having to check whether the string is a palindrome or not.

First, if we are inserting a character at i^{th} position and want this to be a valid position, we should ensure that prefix of length i-1 is equal to suffix of length i-1 in the original string. This can be pre-computed in \mathcal{O}(N) time. Another way is to pre-compute the prefix and suffix hashes of the string as F* denoting the hash of prefix of length i and B* denoting the hash of suffix of length i. While validating, we can simply check if F* evaluates to the same value as B*.

Secondly, the character that would be inserted at i^{th} position would now be equal to (N-i-1)^{th} position. The only thing left to validate is whether the substring S[i,N-i-2] is palindrome or not. This can again be pre-computed in a separate array as in: F(i, N-i-2) is palindrome if and only if F(i+1,N-i-3) is palindrome and S* is equal to S[N-i-2]. This can again be done in \mathcal{O}(N). The same thing can also be checked using Prefix and Suffix hashes if pre-computed before. Do not forget to check some corner cases, and when you are inserting the characters at > N/2 positions. You might have to do small changes in the implementation.

If both the checks are valid, then we add +1 to our count of valid positions. Look at the solutions section to see different kinds of implementations for the above mentioned approaches.

### COMPLEXITY:

Solutions of Complexity both \mathcal{O}(N) and \mathcal{O}(NlogN) are considered. However, \mathcal{O}(NlogN) hashing can still be optimized to \mathcal{O}(N) hashing. Do Read this.

Tester’s solution uses an \mathcal{O}(N) approach involving prefix-suffix comparison.