PROBLEM LINK:
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:
- we pick minimal position i such as x[i] and x[n-i+1] differ.
- we delete the character at position i and check if the resulting string is palindrome. If so, we print “YES”.
- we delete the character at position n-i+1 and check if the resulting string is palindrome. If so, we print “YES”.
- Otherwise, we print “NO”.
- 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
