Valid Palindrome II

easyPROHash Maps & DesignMeta DSA

Given a string s, return True if s can be a palindrome after deleting at most one character.

Example

Input

aba

Output

True

Reasoning

Input: s is the string "aba", a sequence of $n = 3$ lowercase letters indexed $0, 1, 2$ .
A string is a palindrome when every character equals its mirror: $s_i = s_{n-1-i}$ for all $i$ . For $n = 3$ the only mirrored pair is positions $0$ and $2$ ; the middle letter at position $1$ pairs with itself.
Here $s_0 = s_2 =$ a, so the pair matches and "aba" is already a palindrome.
Deletions used: $0$ , which satisfies "at most one", so the output is True.
Contrast: "abca" has a mismatched inner pair (b vs c), yet deleting the b leaves "aca" and deleting the c leaves "aba"; more than one deletion can work, so it is still True. "abc" mismatches (a vs c), and every one-letter deletion ("bc", "ac", "ab") leaves a non-palindrome, so it is False.
Notice that the output only says whether some deletion of at most one letter works, not which letter; and the middle letter of an odd-length string never has to match anything.

Constraints

1 <= len(s) <= 10^5
s consists of lowercase English letters

Learn this in

Two Pointers & Sliding WindowDSA Study Plan

More from Meta DSA

Dot Product of Two Sparse Vectorseasy Random Pick with Weightmedium Copy List with Random Pointermedium Remove Nth Node From Endmedium Add Two Numbersmedium

PRO

Editor locked

The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.

solution.py

Python 3.13

Test results

Valid Palindrome II

Example

Constraints

Learn this in

More from Meta DSA

Background Knowledge

Algorithm/Approach

Continue the full explanation

Editor locked