Valid Palindrome II: definition
A palindrome reads the same forward and backward. This task allows removing at most one character to make the string a palindrome.
Task example: Valid Palindrome II
Given a string s of lowercase English letters, return True if it is a palindrome after deleting at most one character; otherwise return False. Zero deletions are allowed. Do not reorder or filter characters.
Unlike Valid Palindrome, this problem already contains only lowercase letters. No cleanup is needed.
Brute force: video explanation
s = "abca" → True
Prefer reading? Follow the steps below.
- First compare s with its reverse. If they match, return True: the string needs no deletion.
- Otherwise, try each index as skip. Build a candidate from the characters before and after skip, always starting from the original string.
- Compare each candidate with its reverse. Return True on the first match. If every candidate fails, return False.
- For abca, removing index 0 gives bca, which fails. Removing index 1 gives aca, which succeeds. Stop immediately.
Time complexity · O(n²)
Up to n candidates each require O(n) work to build, reverse, and compare. Worst-case time complexity is O(n²).
Space complexity · O(n)
Only the current candidate and its reverse are needed. Their size grows with n, so extra space is O(n).
Two pointers: video explanation
s = "abca" → True
Prefer reading? Follow the steps below.
- Start left and right at opposite ends. If the characters match, move both pointers inward.
- At the first mismatch, check the range without the left character OR the range without the right character. The helper compares endpoints without allowing another deletion.
- For abca, a matches a. At b versus c, skip b: the remaining c is a palindrome, so return True. The or expression stops after the first successful check.
- Try abccdba to see both branches: skipping the left c fails, but skipping the right d succeeds. For abc, both choices fail.
Why it works: matching outer characters leave only the inner range. At its first mismatch, one of the two endpoints must be removed. Checking both choices avoids the brute-force search over every index.
Time complexity · O(n)
The main scan and at most two helper scans are linear. A fixed number of O(n) scans is O(n), improving on brute-force O(n²) time.
Space complexity · O(1)
The helper uses indices into s, with no substring copies or recursion. Extra space is O(1), compared with O(n) for brute force.