Valid Palindrome II

Given a string s, return true if the string can become a palindrome after deleting at most one character.

You may choose to delete one character or delete nothing at all.

Brute Force

A straightforward approach is to try deleting every character one by one.

For every possible deletion:

1. Delete one character.
2. Check whether the resulting string is a palindrome.
3. Return true if any deletion produces a palindrome.

There can be n possible characters to delete, and each palindrome check can take O(n) time.

Therefore, the worst-case complexity is:

Time: O(n²)

Space: O(n)

We can improve this by using two pointers and avoiding the creation of new strings.

Optimal Approach: Two Pointers

Start with two pointers:

• left at the beginning of the string.
• right at the end of the string.

Compare the characters at both positions.

If they match, move both pointers toward the center.

If they do not match, we have found the first position where the palindrome condition is broken.

At this point, because we can delete only one character, there are only two possibilities:

• Delete the character at left.
• Delete the character at right.

We check both possibilities and return true if either remaining substring is a palindrome.

C++ Solution

class Solution {
    public:
    bool check(string& s, int left, int right) {
        while (left < right) {
            if (s[left] != s[right]) {
                return false;
            }

            left++;
            right--;
        }

        return true;
    }

    bool validPalindrome(string s) {
        int left = 0;
        int right = s.length() - 1;

        while (left < right) {
            if (s[left] != s[right]) {
                return check(s, left + 1, right) ||
                check(s, left, right - 1);
            }

            left++;
            right--;
        }

        return true;
    }
};

Why Do We Check Only Two Characters?

Suppose we reach:

1s[left] != s[right]

These two characters are supposed to be mirror images of each other in a palindrome.

Since they are different, both cannot remain in the final palindrome.

Therefore, one of them must be removed.

That gives us exactly two possibilities:

1Remove s[left] Or Remove s[right]

After choosing one, the rest of the substring must already be a palindrome because we have no deletion left.

Why This Is Better Than Brute Force

The brute-force approach tries every possible character as the deletion.

The two-pointer approach waits until a mismatch actually occurs.

Most of the time, the string can be processed normally from both ends. Only when a mismatch appears do we explore the two possible deletion choices.

This reduces the solution from O(n²) to O(n) time.

Complexity

How to Explain It in an Interview