PROBLEM LINK:Author: Sunny Agarwal 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 READINGHashing Tutorial 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. 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 $i1$ is equal to suffix of length $i1$ in the original string. This can be precomputed in $\mathcal{O}(N)$ time. Another way is to precompute the prefix and suffix hashes of the string as $F[i]$ denoting the hash of prefix of length $i$ and $B[i]$ denoting the hash of suffix of length $i$. While validating, we can simply check if $F[i]$ evaluates to the same value as $B[i]$. Secondly, the character that would be inserted at $i$^{th} position would now be equal to $(Ni1)$^{th} position. The only thing left to validate is whether the substring $S[i,Ni2]$ is palindrome or not. This can again be precomputed in a separate array as in: $F(i, Ni2)$ is palindrome if and only if $F(i+1,Ni3)$ is palindrome and $S[i]$ is equal to $S[Ni2]$. This can again be done in $\mathcal{O}(N)$. The same thing can also be checked using Prefix and Suffix hashes if precomputed 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 prefixsuffix comparison. SOLUTIONS:
This question is marked "community wiki".
asked 26 Aug '15, 17:48

Meteora has a very intersting O(n) solution without hashing https://www.codechef.com/viewsolution/7956658 I would be delighted if someone can explain the approach! answered 30 Aug '15, 16:57

How are we calculating whether the string S(i+1, ni2) is palindrome or not? What is the precomputation involved here ? answered 30 Aug '15, 21:00

here is my solution with O(n) without hashing :https://www.codechef.com/viewsolution/7970299 answered 31 Aug '15, 14:53

Another approach for O(n) complexity. For the first half of the string, Let the character be inserted at position j, The prefix would be a palindrome if, bflag = (bflag && (s[j]==s[nj1])) is true. For suffix, we first need to count no. of such locations such that s[j]==s[nj2] for(k=0;k<n/2;k++) if(s[k]==s[nk2]) val++; Each time subtract, s[j]==s[nj2] i.e. 1 or 0 and check if val==(n/2  j) Repeat the same after reversing the string for the later half. Link to the solution : https://www.codechef.com/viewsolution/7959523 answered 31 Aug '15, 17:20
