MAKPALIN - Editorial

editorial
, , , , ,
1

PROBLEM LINK:

Practice
Contest

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 ith 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[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 ith 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[i] 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.

SOLUTIONS:

Tester

1 Like
2

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!

3

Please see tester’s solution for O(n) approach.

4

Could any one better explain the question? What if the input string is abc?
to make it a palindrome the series of steps would be cabc,cabac,cabbac … so the answer is insertion at 3 positions . is this right?

5

How are we calculating whether the string S(i+1, n-i-2) is palindrome or not? What is the pre-computation involved here ?

6

We can insert only one character at a time. Say, for the string aba, we can insert ‘b’ in the second position to make the string a’b’ba which is a palindrome. Another palindrome can be obtained if we insert ‘b’ in third position and the string will be ab’b’a.The inserted character is written within quotes. Another one will be ab?ba where ‘?’ is any character. So, in this case, answer will be 3.
For the string abc, answer will be 0 since we cannot make it a palindrome by inserting a character in any postion.

7

here is my solution with O(n) without hashing :-https://www.codechef.com/viewsolution/7970299

8

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[n-j-1])) is true.
For suffix, we first need to count no. of such locations such that s[j]==s[n-j-2]

for(k=0;k<n/2;k++)
if(s[k]==s[n-k-2])
val++;

Each time subtract, s[j]==s[n-j-2] 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

9

thank u @snk967 . Got it ! Will try now

1 Like