Problem: Convert to Palindrome
Given a string A consisting only of lowercase characters, we need to check whether it is possible to make this string a palindrome after removing exactly one character from this. If it is possible then return 1 else return 0.
3 <= |A| <= 105 A[i] is always a lowercase character.
The first and only argument is string A.
Return 1 if it is possible to convert A to palindrome by removing exactly one character else return 0.
Input 1: A = "abcba" Input 2: A = "abecbea"
Output 1: 1 Output 2: 0
Explanation 1: We can remove character ‘c’ to make string palindrome Explanation 2: It is not possible to make this string palindrome just by removing one character
We can solve this problem by finding the position of mismatch. We start looping in the string by keeping two pointers at both the ends which traverse towards mid position after each iteration, this iteration will stop when we find a mismatch, as it is allowed to remove just one character we have two choices here,
A mismatch, either remove character pointed by the left pointer or remove character pointed by the right pointer.
We will check both the cases, remember as we have traversed an equal number of steps from both sides, this mid string should also be a palindrome after removing one character, so we check two substrings, one by removing the left character and one by removing the right character and if one of them is palindrome then we can make complete string palindrome by removing the corresponding character, and if both substrings are not palindrome then it is not possible to make the complete string a palindrome under given constraint.
Time Complexity: O(N)
Code in CPP