PRPALN - Editorial

PROBLEM LINK:

contest

practice

Author: Praveen Dhinwa

Tester: Sergey Kulik

Editorialist: Florin Chirica

DIFFICULTY:

simple

PREREQUISITES:

greedy

PROBLEM:

You’re given a string. You can pick exactly one character from it and delete it. Can you pick the character such as resulting string is palindrome?

QUICK EXPLANATION

We notice that after we delete a character, the center of the future palindrome candidate doesn’t modify too much: it’s near n / 2. So we can iterate a little number of palindrome centers near n / 2 and then check if we can get a palindrome from that center by deleting exactly one character.

EXPLANATION

When is a string a palindrome?

Let’s start by checking if a string is a palindrome. Suppose the string x has n characters and they are x1, x2, …, x[n]. The string is palindrome if we read it from left to right and from right to left and we obtain the same string. If we read it from left to right, we get string x1x2…x[n]. If we read it from right to left, we get string x[n]x[n-1]…x1. So, x1 needs to be equal to x[n], x2 needs to be equal to x[n-1] and (by same logic) x[i] needs to be equal with x[n-i+1].

Particular case: the initial string is already a palindrome

Let’s start from here. What if our particular string is already a palindrome? If we delete nothing, then we still get a solution. However, the problem forces us to delete exactly a character. It turns out, if the string is from the beginning a palindrome, it can still remain a palindrome after a smart deletion.

Let’s take two examples to illustrate this: string “abcba” can be transformed into “abba” and string “abccba” can be transformed into “abcba”.

Generally, if n is odd, we can delete middle character (x[(n + 1)/2]). If n is even, we can either delete character n/2 or n/2+1. So, if the string is palindrome, we simply print “YES”.

What if string is not initially a palindrome?

This means, there exist at least one position i such as x[i] is different from x[n-i+1]. In the final string, characters x[i] and x[n-i+1] aren’t allowed to be both on positions i and n-i+1. Let’s take minimal i such as x[i] and x[n-i+1] differ. The only way characters from position i and from position n-i+1 would match is to delete either character from position i or character from position n-i+1. But doing this, we already used our deletion. So, we’re forced to check if the two resulting strings are palindrome. If at least one of them is, we print “YES”. Otherwise, we print “NO” (we’ve used our deletion to fix positions i and n-i+1, however since the resulting strings are not a palindrome, we need extra deletions to fix the resulting strings; however, we’re allowed to do only one deletion).

So, the algorithm goes as following:

  1. we pick minimal position i such as x[i] and x[n-i+1] differ.
  2. we delete the character at position i and check if the resulting string is palindrome. If so, we print “YES”.
  3. we delete the character at position n-i+1 and check if the resulting string is palindrome. If so, we print “YES”.
  4. Otherwise, we print “NO”.
  5. Since each step takes O(n) time, our complexity is O(n) for each string from the input.

Why does it work?

It seems we found a functional algorithm. However, we haven’t proved yet it works. We need to proof that, if we delete positions i and n-i+1 and we don’t get a solution, then we won’t get a solution after deleting any other position i’. In other words, we need to proof that if a solution exists for deleting position i’, then it will exist also for deleting position i or position n-i+1.

Let’s see how the matching is done after we delete a position. I’ll assume for simplicity we delete only positions i <= n-i+1 (other case is treated similar).

So, let’s have string x1x2x3x4x5x[6]x[7]x[8]. Let i = 3 be the first position such as x[i] != x[n-i+1]. Let’s try to do another delete, at a position other than 3 or 8-3+1 = 6.

First of all, let’s try to delete i’ such as i < i’ < n - i + 1. In this case, no palindrome can be formed, because x[i] will still be different from x[n-i+1]. For our example, deleting i’ = 4, the new array will be x1x2x3x5x[6]x[7]x[8]. As you can see, 3rd position will still correspond to x[6] (and as x3 != x[6], so palindrome isn’t good).

I’ll take only case i’ < i. Suppose by deleting i’ = 2, we obtain a palindrome. Let’s proof then, that by deleting i = 3 we also obtain a palindrome (from this particular example you can do a generalization / formal proof).

Deleting i’ = 2, we get x1x3x4x5x[6]x[7]. So we know that x1 = x[7], x3 = x[6], x4 = x5 (since deleting i’ resulted a palindrome).

Let’s delete now at i = 3. We get x1x2x4x5x[6]x[7]. This means x1 = x[7], x2 = x[6], x4 = x5. Since i = 3, we already know first 2 conditions are true. From i’ = 2 being a palindrome, we also know x4 = x5 as true. So, we delete position i’ and obtain a palindrome. As we showed, deleting position i also gives a palindrome.

Generally, suppose deleting at i’ gives a palindrome. This will ensure us that x[i+1] = x[n-i+2], x[i+2] = x[n-i+3] and so on. Also, deleting exactly position i will ensure us that x1 = x[n], x2 = x[n - 1], …, x[i - 1] = x[n - i + 2]. So, array x1x2…x[i-1]x[i+1]…x[n] is a palindrome.

We proved that if a solution exists for i’, then it exists either for i or n - i + 1. Hence, it’s enough to check if a solution exists only for i or n - i + 1.


Author’s Solution

Few valid choices for centre of palindrome?
You can notice that the string’s length after the deletion will reduce by 1. So if we think about the position of centre in the constructed
palindrome, it will be near n / 2. It won’t be very far from it.
So we can try considering few positions near half of the string length as possible candidates for the centre of the desired palindrome.

How to check after fixing the centre
After fixing the centre, we just have to check whether the resulting string can be a palindrome around that centre. We will try to find
first position where the character’s differ and make the string non-palindrome. As explained in previous part, there will be at most two such positions,
We will try to remove those characters one by one and will check whether the resulting string is palindrome or not.

Time Complexity
All the steps are just iterating over the string, deleting few characters and checking whether a string is palindrome or not? All these steps
can be done in O(n) where n is the length of the string. Note that here constant factor of the algorithm matters, but author has set a pretty relaxed time
limit to ensure high constant factor solution to pass too.

Subtasks Solutions

Subtask 1

You can iterate over the characters which you want to delete from the string. After deleting check whether the string is palindrome or not.

Pseudo Code

ok = false;
for i = 0 to n:
	string s' = delete s[i] from s.
	if (isPalindrome(s')):
		ok = true;

Time Complexity
We are iterating over the string and for each iteration, we are deleting the i^th character and constructing new string s’ and checking whether the s’ is palindrome or not.
Deleting a character and checking a string is palindrome or not will take O(n) time. We are doing this for each character, so O(n) time for external
loop, So overall time taken will be O(n^2).

Subtask 2

It is same as the main solution of O(n) time explained above.

AUTHOR’S AND TESTER’S SOLUTIONS:

To be updated soon
To be updated soon

2 Likes

Please check this solution, I seem to be using the same algorithm as described by you. If you can give me some or one of the test cases where my code fails, that would be highly appreciated.
http://www.codechef.com/viewsolution/5336073
Thank you.

1 Like

@thegreatheisenberg Here’s a test case for which your code gives incorrect answer…
ololllollo
Answer should be YES… yours giving NO

2 Likes

I would say, if you code prints YES for inputs:

X010
0X10
01X0
010X
X0110
0X110
01X10
011X0
0110X

and NO for inputs:

YX010
XY010
X0Y10
X01Y0
X010Y
Y0X10
0YX10
0XY10
0X1Y0
0X10Y
Y01X0
0Y1X0
01YX0
01XY0
01X0Y
Y010X
0Y10X
01Y0X
010YX
010XY

It should be ok , generated with - http://ideone.com/3N7D2h .

I know that in input only ‘a’…‘z’ should be, but it shouldn’t matter for correct algorithm.

Please help me, why this code is not passing for all test case?-code link link

1 Like

I tried your code with all test cases I wrote above - http://ideone.com/AqSH1H

One of failing ones is: YES for X01Y10

Amongst the test cases uploaded by betlista, I think there are two in-accuracies. X01Y10 can be converted to a palindrome by deleting exactly one character - X.

Similarly Y01X10 can be converted to a palindrome by deleting Y.

Am I missing out something here?

2 Likes

are the problems added to practice sections?

1 Like

yes, they have been added to the practice section. This must be in the easy sub-section.

This problem can be solved in O(n) time.

You scan the string from left to right, right to left, middle to left, middle to right.

The main idea, is that you have S[i]=S[L-1-i] or S[L-2-i] if you remove an element on the right.

See code here: http://www.codechef.com/viewsolution/5305313

1 Like

You are correct, my bad, I have to edit the post…

Here is my solution:
http://www.codechef.com/viewsolution/5292391

I am still not able to figure out a case where it is failing.
All test cases mentioned by @betlista is passing.

1 Like

PRPALN is not available anywhere in practice section. Please fix it. Provide the link if iam wrong.

I have followed exactly the same algorithm but it is still failing for some test cases. Please somebody clarify and douse my curiosity. Here is my solution: http://www.codechef.com/viewsolution/5343041

for

1
X0Y10

your code returns YES

is the problem there in the practice section ?

I added links :wink:

I added links :wink:

I added links :wink:

my code is giving correct answers for all testcases yet I am getting a wrong answer when submitting plzzz help

here is the link to my code
http://ideone.com/5F4fPP