LeetCode 680 - Valid Palindrome II

Difficulty: 🟢 Easy
Topics: Two Pointers, String, Greedy

Solution

Problem Understanding

The problem asks whether a given string s can become a palindrome after deleting at most one character.

A palindrome is a string that reads the same forwards and backwards. For example, "aba" and "racecar" are palindromes because their characters match symmetrically from both ends.

The input consists of a single string s made only of lowercase English letters. The output is a boolean value:

Return true if the string is already a palindrome, or if removing one character or zero characters can make it a palindrome.
Return false if it would require removing more than one character.

For example, "abca" returns true because removing 'c' produces "aba", which is a palindrome. However, "abc" returns false because removing only one character still leaves a non-palindrome string.

The constraint 1 <= s.length <= 10^5 is particularly important. A string length of 100,000 means algorithms with quadratic time complexity, such as checking every possible deletion separately, will likely be too slow. This strongly suggests we need an efficient linear-time approach.

Several edge cases deserve attention. Strings that are already palindromes should immediately return true. Very short strings such as length 1 or 2 should also work correctly, since removing zero or one character trivially produces a palindrome. Another important case is when the first mismatch appears, because we only get one deletion opportunity, so choosing the correct character to skip becomes critical.

Approaches

Brute Force Approach

A straightforward way to solve this problem is to try removing every possible character one at a time and check whether the resulting string is a palindrome.

For a string of length n, we would generate n modified strings. Each palindrome check requires scanning the string, which takes O(n) time. Since we repeat this for every index, the total time complexity becomes O(n²).

This approach is correct because it exhaustively checks every valid deletion possibility, including the case where no deletion is needed. However, with n = 10^5, quadratic time is too slow.

Optimal Approach, Two Pointers with Greedy Validation

The key observation is that a palindrome only fails when characters at symmetric positions stop matching.

We can use two pointers:

One pointer starts at the left end.
One pointer starts at the right end.

As long as the characters match, we continue moving inward. If we encounter a mismatch, we only have one deletion available, so there are exactly two possibilities:

Skip the left character.
Skip the right character.

If either resulting substring forms a palindrome, the answer is true.

This works because the first mismatch is the only place where a deletion matters. Before that point, the prefix and suffix already match perfectly, so deleting elsewhere would not help resolve the mismatch.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Try deleting every character and check palindrome
Optimal	O(n)	O(1)	Two pointers with at most one validation pass

Algorithm Walkthrough

Initialize two pointers, left at the beginning of the string and right at the end.
Move both pointers inward while the characters match. This works because matching characters are already valid palindrome pairs and need no modification.
If the pointers cross or meet without mismatches, return true. The string is already a palindrome.
If a mismatch occurs at positions left and right, we must decide whether removing one character can fix the string.
Check whether skipping the left character creates a palindrome by validating the substring s[left + 1:right + 1].
Check whether skipping the right character creates a palindrome by validating the substring s[left:right].
Return true if either check succeeds. Otherwise, return false.

To validate whether a substring is a palindrome, use another helper function with two pointers. It scans inward and returns false immediately upon mismatch.

Why it works

The correctness comes from the fact that the first mismatch is the only meaningful decision point. Before that mismatch, all characters already satisfy the palindrome condition. Since only one deletion is allowed, the only reasonable choices are removing either the left mismatched character or the right mismatched character. If neither option produces a palindrome, no valid solution exists.

Python Solution

class Solution:
    def validPalindrome(self, s: str) -> bool:
        def is_palindrome(left: int, right: int) -> bool:
            while left < right:
                if s[left] != s[right]:
                    return False
                left += 1
                right -= 1
            return True

        left = 0
        right = len(s) - 1

        while left < right:
            if s[left] != s[right]:
                return (
                    is_palindrome(left + 1, right)
                    or is_palindrome(left, right - 1)
                )

            left += 1
            right -= 1

        return True

The implementation begins by defining a helper function, is_palindrome, which checks whether a substring between two indices forms a palindrome. Instead of creating a new substring, it works directly with indices, avoiding unnecessary memory usage.

The main logic uses two pointers to compare characters from both ends of the string. When characters match, both pointers move inward.

If a mismatch occurs, the algorithm immediately tries the only two valid possibilities: skipping the left character or skipping the right character. The helper function verifies whether either remaining substring is a palindrome.

If no mismatches are found, the original string is already a palindrome, so the function returns True.

Go Solution

func validPalindrome(s string) bool {
	isPalindrome := func(left, right int) bool {
		for left < right {
			if s[left] != s[right] {
				return false
			}
			left++
			right--
		}
		return true
	}

	left := 0
	right := len(s) - 1

	for left < right {
		if s[left] != s[right] {
			return isPalindrome(left+1, right) ||
				isPalindrome(left, right-1)
		}

		left++
		right--
	}

	return true
}

The Go implementation follows the same logic as the Python version. A local helper function checks whether a substring is a palindrome using indices rather than slicing, which avoids unnecessary allocations.

Go strings are byte indexed, which is safe here because the problem guarantees lowercase English letters only. Since only ASCII characters are used, indexing by byte works correctly.

No special handling for integer overflow is necessary because indices remain within string bounds.

Worked Examples

Example 1

Input: s = "aba"

Initial state:

Step	Left	Right	Characters	Action
1	0	2	`a`, `a`	Match, move inward
2	1	1	Same index	Stop

No mismatch occurs, so the string is already a palindrome.

Output: true

Example 2

Input: s = "abca"

Initial state:

Step	Left	Right	Characters	Action
1	0	3	`a`, `a`	Match, move inward
2	1	2	`b`, `c`	Mismatch found

At the mismatch:

Skip left (b): substring "ca" → not palindrome
Skip right (c): substring "bc"? Actually checking indices gives "aba" structure → palindrome

Validation:

Option	Result
Remove `b`	False
Remove `c`	True

Since one option succeeds:

Output: true

Example 3

Input: s = "abc"

Initial state:

Step	Left	Right	Characters	Action
1	0	2	`a`, `c`	Mismatch found

Try both possibilities:

Option	Remaining String	Result
Remove `a`	`"bc"`	Not palindrome
Remove `c`	`"ab"`	Not palindrome

Neither works.

Output: false

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	The main scan is linear, and at most one additional palindrome check scans part of the string
Space	O(1)	Only a few pointers and variables are used

Although the helper function may scan part of the string again after a mismatch, this only happens once. Therefore, the total work still remains linear, not quadratic.

Test Cases

solution = Solution()

assert solution.validPalindrome("aba") is True  # already palindrome
assert solution.validPalindrome("abca") is True  # remove one character
assert solution.validPalindrome("abc") is False  # impossible with one deletion

assert solution.validPalindrome("a") is True  # single character
assert solution.validPalindrome("aa") is True  # two matching characters
assert solution.validPalindrome("ab") is True  # remove one character

assert solution.validPalindrome("deeee") is True  # remove first character
assert solution.validPalindrome("eeeed") is True  # remove last character
assert solution.validPalindrome("raceacar") is True  # remove one middle character

assert solution.validPalindrome("abcdef") is False  # multiple mismatches
assert solution.validPalindrome("cbbcc") is True  # delete one internal character
assert solution.validPalindrome("aguokepatgbnvfqmgmlcupuufxoohdfpgjdmysgvhmvffcnqxjjxqncffvmvhgvsymdjgpfdhooxfuupuculmgmqfvnbgtapekouga") is True  # stress test

Test	Why
`"aba"`	Verifies already-palindrome input
`"abca"`	Validates single deletion in middle
`"abc"`	Confirms impossible case
`"a"`	Smallest valid input
`"aa"`	Two-character palindrome
`"ab"`	One deletion allowed
`"deeee"`	Tests deleting first character
`"eeeed"`	Tests deleting last character
`"raceacar"`	Tests middle deletion
`"abcdef"`	Multiple mismatches fail
`"cbbcc"`	Internal mismatch handling
Long stress test	Validates efficiency for large inputs

Edge Cases

One important edge case is a string that is already a palindrome. A buggy implementation might force a deletion unnecessarily or mishandle the termination condition. For example, "aba" should immediately return true. The implementation handles this naturally because the two pointers meet without encountering a mismatch.

Another important case is when the removable character appears at the beginning or end of the string. Inputs such as "deeee" or "eeeed" require skipping one boundary character. Some implementations incorrectly assume deletions only happen in the middle. Here, both skip possibilities are checked, so boundary removals work correctly.

A third tricky case occurs when the first mismatch offers two possible deletions, but only one is correct. For example, "abca" requires removing 'c', not 'b'. A greedy approach that only tries one side would fail. This implementation explicitly checks both possibilities and returns true if either produces a palindrome.

A final edge case is very large input strings near the limit of 10^5 characters. A quadratic solution could time out. Since this implementation performs only a constant number of linear scans, it remains efficient even for the largest allowed inputs.