Convert to Palindrome

Problem: Convert to Palindrome

Problem Statement:

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.

Problem Constraints

3 <= |A| <= 105
A[i] is always a lowercase character.

Input Format

The first and only argument is string A.

Output Format

Return 1 if it is possible to convert A to palindrome by removing exactly one character else return 0.

Example Input

Input 1:
 A = "abcba" 
Input 2:
 A = "abecbea" 

Example Output

Output 1:
 1 
Output 2:
 0 

Example Explanation

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 

Approach

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)

Solution

Code in CPP