# LeetCode 680. Valid Palindrome II

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

[English Version in Youtube](https://youtu.be/rNTH2DSW8z0)

[中文版解答Youtube Link](https://youtu.be/w18su7VGwUQ)

[中文版解答Bilibili Link](https://www.bilibili.com/video/BV1Rf4y1W7GE/)

```
class Solution {
public:
    bool validPalindrome(string s) {
        for (int i = 0, j = s.size() - 1; i < j; i++, j--) {
            if (s[i] != s[j]) {
                int i1 = i, j1 = j - 1, i2 = i + 1, j2 = j;
                while (i1 < j1 && s[i1] == s[j1]) {
                    i1++;
                    j1--;
                };
                if (i1 >= j1) {
                    return true;
                }
                while (i2 < j2 && s[i2] == s[j2]) {
                    i2++;
                    j2--;
                };
                if (i2 >= j2) {
                    return true;
                }
                
                return false;
            }
        }
        
        return true;
    }
};
```
