All problems

Valid Palindrome II

Easy · two pointers

A string is a palindrome if it reads the same from left to right as from right to left.

Given a string s, you may delete at most one character from it (or none at all). Return true if the string that is left can be a palindrome, and false if it cannot.

Deleting a character closes the gap, so the remaining characters keep their order. A string of one character is already a palindrome.

Examples

Example 1

Input: s = "abca"

Output: true

Delete the "c" (or the "b") and what is left, "aba" (or "aca"), is a palindrome.

Example 2

Input: s = "abcd"

Output: false

Deleting any single character leaves three different letters, which never read the same both ways.

Example 3

Input: s = "level"

Output: true

It is a palindrome already, so no deletion is needed.

Constraints

• 1 <= len(s) <= 3000
• s consists of lowercase English letters.