Given a string, We have to find out by removing which character, it becomes a palindrome.
For example consider the string “racercar”, the character ‘r’ at index 4 should be removed to become a palindrome.
The approach here is simple.
For example consider the string “racercar”, the character ‘r’ at index 4 should be removed to become a palindrome.
The approach here is simple.
Start from both ends of the string and compare both characters. If they are equal, we increment the front index and decrement the back index. If they are not equal, one of the characters needs to be removed. We can check this by verifying if a palindrome can be formed by removing the front character or the back character. Repeat the above procedure until both indices meet each other.
We are printing the index of the character to be removed. If the string is already a palindrome, we print -1.
This solution has O(n) time complexity.
Here are the implementations in C++.