## 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.

b'
\n\n

#### Approach #1: Brute Force [Time Limit Exceeded]

\n

Intuition and Algorithm

\n

For each index `i` in the given string, let\'s remove that character, then check if the resulting string is a palindrome. If it is, (or if the original string was a palindrome), then we\'ll return `true`

\n\n

Complexity Analysis

\n
\n
• \n

Time Complexity: where is the length of the string. We do the following times: create a string of length and iterate over it.

\n
• \n
• \n

Space Complexity: , the space used by our candidate answer.

\n
• \n
\n
\n

#### Approach #2: Greedy [Accepted]

\n

Intuition

\n

If the beginning and end characters of a string are the same (ie. `s[0] == s[s.length - 1]`), then whether the inner characters are a palindrome (`s[1], s[2], ..., s[s.length - 2]`) uniquely determines whether the entire string is a palindrome.

\n

Algorithm

\n

Suppose we want to know whether `s[i], s[i+1], ..., s[j]` form a palindrome. If `i >= j` then we are done. If `s[i] == s[j]` then we may take `i++; j--`. Otherwise, the palindrome must be either `s[i+1], s[i+2], ..., s[j]` or `s[i], s[i+1], ..., s[j-1]`, and we should check both cases.

\n\n

Complexity Analysis

\n
\n
• \n

Time Complexity: where is the length of the string. Each of two checks of whether some substring is a palindrome is .

\n
• \n
• \n

Space Complexity: additional complexity. Only pointers were stored in memory.

\n
• \n
\n
\n

Analysis written by: @awice

\n
'