Approach #1: Brute Force [Time Limit Exceeded]
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

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

Space Complexity: , the space used by our candidate answer.
Approach #2: Greedy [Accepted]
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[j1]
, and we should check both cases.
Complexity Analysis

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

Space Complexity: additional complexity. Only pointers were stored in memory.
Analysis written by: @awice