Removal of a character to make a string a palindrome 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 &lt;iostream&gt;
#include &lt;string&gt;
using namespace std;

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

   int main() {

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

   }
   return 0;
  }
Some Improvements:


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
A minor improvement: do you need to iterate over the entire string to determine if it is a palindrome?