#680

Easy

auto_awesomeTwo-pointer scanning with invariant tracking

LeetCode Problem Workspace

Valid Palindrome II

Check if a string can become a palindrome by deleting at most one character using two-pointer scanning and invariant tracking.

two pointers string greedy

Problem Statement

Given a string s, return true if it can be a palindrome after deleting at most one character. A palindrome is a word, phrase, number, or other sequence of characters that reads the same forward and backward.

Implement a solution where you use two pointers to check if characters at both ends are equal. If they are not, try removing one character at either pointer and check if the result is a palindrome.

Examples

Example 1

Input: s = "aba"

Output: true

Example details omitted.

Example 2

Input: s = "abca"

Output: true

You could delete the character 'c'.

Example 3

Input: s = "abc"

Output: false

Example details omitted.

Constraints

1 <= s.length <= 105
s consists of lowercase English letters.

Solution Approach

Two-pointer scanning

Start by using two pointers at the beginning and the end of the string. If the characters at these positions match, move both pointers inward. If they don’t match, check if removing one character at either position allows the string to become a palindrome.

Invariant tracking

Track the invariant that the string must be a palindrome after removing one character. At each mismatch, ensure that deleting a character at either pointer creates a valid palindrome for the remaining string.

Greedy approach

Apply a greedy method to remove a character at the first mismatch. Check if skipping one character creates a valid palindrome. If not, return false immediately.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is O(n) because each pointer moves across the string at most once. The space complexity is O(1), as the solution uses constant extra space beyond the input string.

What Interviewers Usually Probe

Candidate should demonstrate a clear understanding of two-pointer techniques.
Look for how well the candidate handles the one-character deletion requirement.
Evaluate the ability to optimize and keep the solution space-efficient.

Common Pitfalls or Variants

Common pitfalls

Not handling the case when characters match early but fail when removing one.
Over-complicating the solution by using extra data structures like arrays or sets.
Missing edge cases like strings that are already palindromes or too short to modify.

Follow-up variants

Check if the string can be a palindrome with two or more deletions.
Use this technique with longer strings for performance optimization.
Consider case sensitivity when expanding the problem scope.

FAQ

What is the time complexity of Valid Palindrome II?

The time complexity is O(n) because the two-pointer technique scans the string once.

How does the two-pointer approach work for this problem?

The two-pointer approach compares characters from both ends and moves inward, allowing for one character deletion if a mismatch occurs.

What is the maximum length of string `s` in Valid Palindrome II?

The maximum length of s is 10^5, which requires an efficient O(n) solution.

Can Valid Palindrome II handle strings that are already palindromes?

Yes, if the string is already a palindrome, the solution will return true without any deletions.

What is the space complexity of Valid Palindrome II?

The space complexity is O(1), as the solution uses only constant extra space beyond the input string.

terminal

Solution

Solution 1: Two Pointers

We use two pointers to point to the left and right ends of the string, respectively. Each time, we check whether the characters pointed to by the two pointers are the same. If they are not the same, we check whether the string is a palindrome after deleting the character corresponding to the left pointer, or we check whether the string is a palindrome after deleting the character corresponding to the right pointer. If the characters pointed to by the two pointers are the same, we move both pointers towards the middle by one position, until the two pointers meet.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def validPalindrome(self, s: str) -> bool:
        def check(i, j):
            while i < j:
                if s[i] != s[j]:
                    return False
                i, j = i + 1, j - 1
            return True

        i, j = 0, len(s) - 1
        while i < j:
            if s[i] != s[j]:
                return check(i, j - 1) or check(i + 1, j)
            i, j = i + 1, j - 1
        return True

Continue Practicing

#763 partition labels #942 di string match #1147 longest chunked palindrome decomposition