×

# MAKPALIN - Editorial

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

Easy Medium

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.

# 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[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 $(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

This question is marked "community wiki".

20421223
accept rate: 0%

1.3k156581

 0 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 65●2 accept rate: 10% Please see tester's solution for O(n) approach. (30 Aug '15, 19:27)
 0 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? answered 30 Aug '15, 20:32 3★fool_01 1●1 accept rate: 0% 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. (31 Aug '15, 01:35) snk9674★ 1 thank u @snk967 . Got it ! Will try now (31 Aug '15, 21:29) fool_013★
 0 How are we calculating whether the string S(i+1, n-i-2) is palindrome or not? What is the pre-computation involved here ? answered 30 Aug '15, 21:00 4★ps06756 18●1●2 accept rate: 9%
 0 here is my solution with O(n) without hashing :-https://www.codechef.com/viewsolution/7970299 answered 31 Aug '15, 14:53 5★admin123 1.2k●12 accept rate: 28%
 0 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
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,852
×1,722
×354
×344
×145
×113

question asked: 26 Aug '15, 17:48

question was seen: 3,737 times

last updated: 31 Aug '15, 21:40