Find if we can get palindrome

Question

Given a string S.We need to tell if we can make it to palindrome by removing exactly one letter from it or not. I have a O(N^2) approach by modifying Edit Distance method.Is their any better way ?

My Approach :

int ModifiedEditDistance(const string& a, const string& b, int k) {
    int i, j, n = a.size();
    int dp[MAX][MAX];
    memset(dp, 0x3f, sizeof dp);    
    for (i = 0 ; i < n; i++)
        dp[i][0] = dp[0][i] = i;

    for (i = 1; i <= n; i++) {
        int from = max(1, i-k), to = min(i+k, n);
        for (j = from; j <= to; j++) {
            if (a[i-1] == b[j-1])           // same character
                dp[i][j] = dp[i-1][j-1];    
            // note that we don't allow letter substitutions

            dp[i][j] = min(dp[i][j], 1 + dp[i][j-1]); // delete character j
            dp[i][j] = min(dp[i][j], 1 + dp[i-1][j]); // insert character i
        }
    }
    return dp[n][n];
}

How to improve space complexity as max size of string can go upto 10^5.

Please help.

Example : Let String be abc then answer is "NO" and if string is "abbcbba then answer is "YES"

Answer 1

The key observation is that if the first and last characters are the same then you needn't remove either of them; which is to say that xSTRINGx can be turned into a palindrome by removing a single letter if and only if STRING can (as long as STRING is at least one character long).

You want to define a method (excuse the Java syntax--I'm not a C++ coder):

boolean canMakePalindrome(String s, int startIndex, int endIndex, int toRemove);

which determines whether the part of the string from startIndex to endIndex-1 can be made into a palindrome by removing toRemove characters.

When you consider canMakePalindrome(s, i, j, r), then you can define it in terms of smaller problems like this:

1. If j-i is 1 then return true; if it's 0 then return true if and only if r is 0. The point here is that a 1-character string is a palindrome regardless of whether you remove a character; a 0-length string is a palindrome, but can't be made into one by removing a character (because there aren't any to remove).
2. If s[i] and s[j-1] are the same, then it's the same answer as canMakePalindrome(s, i+1, j-1, r).
3. If they're different, then either s[i] or s[j-1] needs removing. If toRemove is zero, then return false, because you haven't got any characters left to remove. If toRemove is 1, then return true if either canMakePalindrome(s, i+1, j, 0) or canMakePalindrome(s, i, j-1, 0). This is because you're now testing whether it's already a palindrome if you remove one of those two characters.

Now this can be coded up pretty easily, I think.

If you wanted to allow for removal of more than one character, you'd use the same idea, but using dynamic programming. With only one character to remove, dynamic programming will reduce the constant factor, but won't reduce the asymptotic time complexity (linear in the length of the string).

Answer 2

Psudocode (Something like this I havn't tested it at all).

It is based on detecting the conditions that you CAN remove a character, ie

1. There is exactly 1 wrong character
2. It is a palendrome (0 mismatch)

O(n) in time, O(1) in space.

 bool foo(const std::string& s)
 {
   int i = 0;
   int j = s.size()-1;
   int mismatch_count = 0;
   while (i < j)
   {
       if (s[i]==s[j])
       {
          i++; j--;
       }
       else
       {
          mismatch_count++;
          if (mismatch_count > 1) break;
          //override first preference if cannot find match for next character
          if (s[i+1] == s[j] && ((i+2 >= j-1)||s[i+2]==s[j-1]))
          {
             i++;
          }
          else if (s[j-1]==s[i])
          {
             j--;
          }
          else
          {
             mismatch_count++; break;
          }
       }
    }  
    //can only be a palendrome if you remove a character if there is exactly one mismatch
    //or if a palendrome
    return (mismatch_count == 1) || (mismatch_count == 0);
 }

Answer 3

Here's a (slightly incomplete) solution which takes O(n) time and O(1) space.

// returns index to remove to make a palindrome; string::npos if not possible
size_t willYouBeMyPal(const string& str)
{
  size_t toRemove = string::npos;
  size_t len = str.length();

  for (size_t c1 = 0, c2 = len - 1; c1 < c2; ++c1, --c2) {
    if (str[c1] != str[c2]) {
      if (toRemove != string::npos) {
        return string::npos;
      }

      bool canRemove1 = str[c1 + 1] == str[c2];
      bool canRemove2 = str[c1] == str[c2 - 1];
      if (canRemove1 && canRemove2) {
        abort(); // TODO: handle the case where both conditions are true
      } else if (canRemove1) {
        toRemove = c1++;
      } else if (canRemove2) {
        toRemove = c2--;
      } else {
        return string::npos;
      }
    }
  }

  // if str is a palindrome already, remove the middle char and it still is
  if (toRemove == string::npos) {
    toRemove = len / 2;
  }

  return toRemove;
}

Left as an exercise is what to do if you get this:

abxyxcxyba

The correct solution is:

ab_yxcxyba

But you might be led down a bad path:

abxyxcx_ba

So when you find the "next" character on both sides is a possible solution, you need to evaluate both possibilities.

Answer 4

I wrote a sample with O(n) complexity that works for the tests I threw at it. Not many though :D The idea behind it is to ignore the first and last letters if they are the same, deleting one of them if they are not, and reasoning what happens when the string is small enough. The same result could be archived with a loop instead of the recursion, which would save some space (making it O(1)), but it's harder to understand and more error prone IMO.

bool palindrome_by_1(const string& word, int start, int end, bool removed = false)  // Start includes, end excludes
{
    if (end - start == 2){
        if (!removed)
            return true;

        return word[start] == word[end - 1];
    }

    if (end - start == 1)
        return true;


    if (word[start] == word[end - 1])
        return palindrome_by_1(word, start + 1, end - 1, removed);

    // After this point we need to remove a letter
    if (removed) 
        return false;

    // When two letters don't match, try to eliminate one of them
    return palindrome_by_1(word, start + 1, end, true) || palindrome_by_1(word, start, end - 1, true);

}