Removal of a character to make a string a palindrome

Question

This code determines which index for a given string if that character is removed will produce a palindrome string.

For eg s = "baa" After removing b the string "aa" is palindrome.

Here this is what I have written until now. Due to time complexity problems, it exceeds 2ms. How this can be made faster?

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

bool checkPalindrome(string s){
  bool found = true;
  int len = s.length();
  for(int i=0;i<len;i++){
    if(s[i] != s[len-i-1])
    {
      found = false;
      break;
    }
   }
  return found;
 }  // end of function

   int main() {

     int test;
     cin>>test;   // get the number of test case
     for(int i=0;i<test;i++){
       string s;
       cin>>s;    // get the string as input
       if(checkPalindrome(s)){
         cout<<-1<<endl;   //if already string is palindrome
       }
       else{
         int len = s.length();
         for(int i=0;i<len;i++){
           string aa = s.substr(0,i) + s.substr(i+1,len);
           if(checkPalindrome(aa)){
             cout<<i<<endl;
             break;
           }
       } 
     }

   }
   return 0;
  }

Answer 1

bool checkPalindrome(string s){
  bool found = true;
  int len = s.length();
  for(int i=0;i<len;i++){
    if(s[i] != s[len-i-1])
    {
      found = false;
      break;
    }
   }
  return found;
 }  // end of function

Since this function is called n times where n is the length of the string, and there are t strings, it is called roughly n*t times, so it is where a bottleneck has a good chance of forming

There is no real need for a comment to say when a function ends, as good indentation will tell you that anyway.

So, we are checking if the two characters from either end are equal, and if they aren't it goes like this

found = false;
break;
return false;

Which is just the same as

return false;

If it makes it through the loop, we should just return true

The second thing of note is the definition of a palindrome, here are two ways of looking at it

1. When you reverse the string, it remains the same
2. The first half and the reverse of the second half are the same

In other words, you only need to look each half once, at the moment you are checking the first and the second half, and then the second and the first half again. We can stop sooner

bool checkPalindrome(string s){
  int len = s.length()/2; //only need to check half the string
  for(int i=0;i<len;i++){
    if(s[i] != s[len-i-1])
    {
      return false
    }
  }
  return true;
}

So the updated version looks like that, and it should be roughly twice as fast for input that are palindromes.

---

To get a real boost though, we need to look at the algorithm itself

If we passed in "aabbcaa" currently it would loop through the string once to check if its a palindrome, and another 5 times before it finds the answer. While it is still O(n) best case, it is O(n^2) in the worst. For larger strings that is a nightmare

So lets try and come up with something better

looping through the string

aabbcaa
-     - 

these are equal so its fine so far

aabbcaa
 -   -  

still all good

aabbcaa
  - -    

these two are different, so we know that one of these two must go*

This gives us two choices "aabbaa" or "aabcaa"

We can pass both of these in to our checkPalindrome function and we have an answer, and in roughly half the time (average case)

*assuming that the string can be made into a palindrome with the removal of 1 or less characters.

Answer 2

Some Improvements:

1. Your checkPalindrome function is returning whether the string is a palindrome or not. What if it returns an index, at which it fails? Try working with that. Right now, you are calling the checkPalindrome function O(string-length), and checkPalindrome in itself is O(string-length), making it a square time algorithm.

   Wikipedia article on Big O notation

2. A minor improvement: do you need to iterate over the entire string to determine if it is a palindrome?

Answer 3

Not about performance, but the palindrome check should really be:

bool is_palindrome(string text) {
    return text == text.reverse() // Or similar
}

It is more similar to the definition.

You need a function to determine the index, stuffing so much code in main is not reccomended.