Remove only one element to make a string palindrome

Question

I will be given string. I can remove only 1 element from it. After removing it if the new string becomes palindrome I have to print "Yes" otherwise "No".

For example, I am given a string "abdbca". Here I can remove 5th index 'c' and make it palindrome and i have to print "Yes". On the other hand if the string is something like "abcd" I can not make it palindrome by removing only one character. Hence I have to print "No".

I tried to do it but my code is not efficient enough. Can anybody please suggest me a efficient way to do it? I have to check strings of 10^5 length in less than 2.5 seconds.

the way I tried to do it is shown bellow :

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>

#define REP(i,n)    for(int i=0;i<n;i++)
#define MAX 100010

using namespace std;

bool isPalindrome(char abc[]){
    int len = strlen(abc), lem = len/2;
    for(int i=0,n=len-1;i<=lem;i++,n--) if(abc[i]!=abc[n]) return false;
    return true;
}

int main()
{
    int tc;
    char str[MAX];
    scanf("%d",&tc);
    while(tc--){
        scanf("%s", str);
        int length = strlen(str), len = length - 1, z = length % 2, res = 0, ans = 0,         b=0,lem = length / 2;
        for(int i = 0;i<length;i++){
            int n=0, m=1;
            for(int x = 0, y = len;x<i && y!=i;x++,y--){
                n++;
                if(str[x]!=str[y]){
                    m=0; ++res;
                    break;
                }
            }
            if(i>lem) for(int x=n,y=len-n-1;x<y;x++,y--){
                if(str[x]!=str[y]){
                    m=0; ++res;
                    break;
                }
            }
            else for(int x=n+1,y=len-n;x<y;x++,y--){
                if(str[x]!=str[y]){
                    m=0; ++res;
                    break;
                }
            }
            if(m==1) {printf("YES\n");b++;break;}
        }
        //if(length <= res) printf("NO\n");
        if(b==0) printf("NO\n");
    }
    return 0;
}

Answer 1

You can refer complete program in c++ here. Input the string to get the index of character to be removed. String reversal is performed in palim() function. It returns -1 if string is already palindrome.

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

bool palim(string s)
{
    string s2;
    s2=string(s.rbegin(),s.rend());
    if(s2==s)
    {
        return true;
    }
    else
    {
        return false;
    }
}
int check(string s)
{
    int x;
        if(s.length()%2==0)
        {
            for(int i=0,j=s.length()-1;i<s.length()/2,j>=s.length()/2;i++,j--)
            {
                if(s[i]!=s[j])
                {
                    string s1=s;
                    s1.erase(j,1);
                    if(palim(s1))
                    {
                        x=j;
                        break;
                    }
                    else
                    {
                        string s1=s;
                        s1.erase(i,1);
                        if(palim(s1))
                        {
                            x=i;
                            break;
                        }
                    }
                }
            }
        }
        else
        {

            for(int i=0,j=s.length()-1;i<s.length()/2,j>s.length()/2;i++,j--)
            {

                if(s[i]!=s[j])
                {
                    string s1=s;
                    s1.erase(j,1);

                    if(palim(s1))
                    {

                        x=j;
                        break;
                    }
                    else
                    {
                        string s1=s;
                        s1.erase(i,1);
                        if(palim(s1))
                        {
                            x=i;
                            break;
                        }
                    }
                }
            }
        }
        return x;
}

int main()
{

        string s;
        cin>>s;
        if(palim(s))
        {
            cout<<"-1"<<endl;
        }
        else
        {
            cout<<check(s)<<endl;
        }


    return 0;
}

Answer 2

Similar to turingcomplete, but with sub functions:

bool isPalindrome(std::string::const_iterator& start, std::string::const_iterator& end)
{
    while (start < end) {
        --end;
        if (*start != *end) {
            return false;
        }
        ++start;
    }
    return true;
}

bool test(const std::string& s)
{
    auto start = s.begin();
    auto end = s.end();

    if (isPalindrome(start, end)) {
        // If we remove the middle character of a palindrome,
        // We still have a palindrome.
        return true;
    }
    // Now test if there is a palindrome
    // if we skip the mismatch char from the start or from the end.
    auto start2 = start;
    auto end2 = end;
    ++start2;
    --end;
    return isPalindrome(start, end) || isPalindrome(start2, end2);
}

Live example

Answer 3

Since you you only need to remove one character, you can do so in linear time by modifying palindrome checking. The idea is that you compare characters from the beginning to characters from the end and stop at the first mismatch. If you remove one character from the mismatching pair and get a palindrome, then return true, otherwise return false. I implemented the idea in C++ below.

#include<iostream>
#include<string>

using namespace std;

bool palindromeExists(string s)
{
  int i = 0;
  int j = s.length()-1;
  while(i < j)
  {
      if(s[i] != s[j]) //first mismatch
          break;
      i++;
      j--;
  }

  int tempj = j-1; //remove s[j]
  int tempi = i;
  while(tempi < tempj)
  {
      if(s[tempi] != s[tempj])
          break;

      tempi++;
      tempj--;

  }

  if(tempi >= tempj) //palindrome found?
      return true;

  tempi = i+1; //remove s[i]
  tempj = j;
  while(tempi < tempj)
  {
      if(s[tempi] != s[tempj])
          return false;
      tempi++;
      tempj--;
  }
  return true;
}

int main()
{
  string s = "abca";
  if(palindromeExists(s))
      cout << "YES" << endl;
  else
      cout << "NO" << endl;
  return 0;
}

This should return true if the string is already a palindrome, or if it can be a palindrome after the removal of one character. I hope I didn't miss any corner cases.