You are not logged in. Please login at www.codechef.com to post your questions!

×

MAKPALIN - Editorial

1
2

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 $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".

asked 26 Aug '15, 17:48

prateekg603's gravatar image

5★prateekg603
20421223
accept rate: 0%

edited 30 Aug '15, 19:26

pushkarmishra's gravatar image

4★pushkarmishra
1.3k156581


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!

link

answered 30 Aug '15, 16:57

i_am_what_i_am's gravatar image

6★i_am_what_i_am
652
accept rate: 10%

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

(30 Aug '15, 19:27) pushkarmishra4★

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?

link

answered 30 Aug '15, 20:32

fool_01's gravatar image

3★fool_01
11
accept rate: 0%

edited 30 Aug '15, 20:37

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★

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

link

answered 30 Aug '15, 21:00

ps06756's gravatar image

4★ps06756
1812
accept rate: 9%

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

link

answered 31 Aug '15, 14:53

admin123's gravatar image

5★admin123
1.2k12
accept rate: 28%

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

link

answered 31 Aug '15, 17:20

nikhil96sher's gravatar image

4★nikhil96sher
1
accept rate: 0%

edited 31 Aug '15, 17:21

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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