# 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