This website contains ALL LeetCode **Premium** problems for
**FREE!!**.

All leaked interview problems are collected from Internet.

All leaked interview problems are collected from Internet.

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:TrueExplanation:You could delete the character 'c'.

**Note:**

- 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

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

\n

\n

'
**Intuition and Algorithm**

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`

**Complexity Analysis**

- \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

**Intuition**

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.

**Algorithm**

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.

**Complexity Analysis**

- \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

Analysis written by: @awice

\n