Remove a character from a string to make it a palindrome | C / C ++ program to check whether it is possible to make string palindrome by removing one character ; Utility method to check if substring from low to high is palindrome or not . ; This method returns - 1 if it is not possible to make string a palindrome . It returns - 2 if string is already a palindrome . Otherwise it returns index of character whose removal can make the whole string palindrome . ; Initialize low and right by both the ends of the string ; loop until low and high cross each other ; If both characters are equal then move both pointer towards end ; If removing str [ low ] makes the whole string palindrome . We basically check if substring str [ low + 1. . high ] is palindrome or not . ; If removing str [ high ] makes the whole string palindrome We basically check if substring str [ low + 1. . high ] is palindrome or not . ; We reach here when complete string will be palindrome if complete string is palindrome then return mid character ; Driver code to test above methods
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool isPalindrome ( string :: iterator low , string :: iterator high ) { while ( low < high ) { if ( * low != * high ) return false ; low ++ ; high -- ; } return true ; } int possiblePalinByRemovingOneChar ( string str ) { int low = 0 , high = str . length ( ) - 1 ; while ( low < high ) { if ( str [ low ] == str [ high ] ) { low ++ ; high -- ; } else { if ( isPalindrome ( str . begin ( ) + low + 1 , str . begin ( ) + high ) ) return low ; if ( isPalindrome ( str . begin ( ) + low , str . begin ( ) + high - 1 ) ) return high ; return -1 ; } } return -2 ; } int main ( ) { string str = " abecbea " ; int idx = possiblePalinByRemovingOneChar ( str ) ; if ( idx == -1 ) cout << " Not ▁ Possible ▁ STRNEWLINE " ; else if ( idx == -2 ) cout << " Possible ▁ without ▁ removing ▁ any ▁ character " ; else cout << " Possible ▁ by ▁ removing ▁ character " << " ▁ at ▁ index ▁ " << idx << " STRNEWLINE " ; return 0 ; }