Question

Given a non-empty string s, you may delete at most one character. Judge whether you can make it a palindrome.

Example 1:

Input: "aba" Output: True

Example 2:

Input: "abca" Output: True Explanation: You could delete the character 'c'.

Note:

1. The string will only contain lowercase characters a-z. The maximum length of the string is 50000.

Solution

// O(n) Time O(1) Space
class Solution {
 public:
  bool validPalindrome(string s) {
    int n = s.length();
    int left = 0, right = n - 1;
    while (left < right) {
      if (s[left++] != s[right--]) return isPalindromic(s, left, right + 1) || isPalindromic(s, left - 1, right);
    }
    return true;
  }

 private:
  bool isPalindromic(string s, int left, int right) {
    while (left < right) {
      if (s[left++] != s[right--]) return false;
    }
    return true;
  }
};