Valid Palindrome II LeetCode 680 Guide

LeetCode 680 — Valid Palindrome II — gives you a string s and asks whether it can become a palindrome by deleting at most one character. A palindrome reads the same forwards and backwards. The key phrase is "at most one" — zero deletions are also valid, meaning any string that is already a palindrome returns true without any deletion.

For example, "abca" returns true because deleting "c" gives "aba", which is a palindrome. The string "abc" returns false because no single deletion can make it a palindrome. The string "raceacar" returns false as well — "racecar" works but that requires deleting two characters. Handling the zero-deletion case is automatic: if two pointers meet without any mismatch, the string was already a palindrome.

The naive approach — try all n possible single deletions and check if any result is a palindrome — runs in O(n^2) time: n deletions each requiring an O(n) palindrome check. For strings up to 10^5 characters, this is too slow. The two-pointer greedy approach handles the problem in O(n) time and O(1) space by identifying the exact deletion point without enumeration.

The two-pointer approach starts with left = 0 and right = len(s) - 1. Move both pointers inward simultaneously, comparing s[left] and s[right] at each step. As long as the characters match, continue: left += 1, right -= 1. If the pointers cross without any mismatch, the string is already a palindrome — return true immediately with no deletion needed.

The critical moment arrives when s[left] != s[right]: a mismatch is detected. This is the only point in the entire scan where a deletion could help. Because we have moved inward symmetrically up to this point, every character outside this mismatch pair is already confirmed to match its mirror. The only characters that could be causing the non-palindrome are s[left] and s[right] themselves.

At the mismatch position we have exactly two candidate deletions: delete the character at left (advance left by 1 and check s[left+1..right]) or delete the character at right (retreat right by 1 and check s[left..right-1]). If either of these two substrings is a palindrome, the answer is true. If neither is, no single deletion can fix the string — return false.

When the two pointers find a mismatch at indices l and r, the algorithm must decide which character to skip. Rather than guessing, it checks both possibilities using a helper function isPalindrome(s, l, r). The first check is isPalindrome(s, l+1, r): this tests what happens if we delete the character at position l. The second check is isPalindrome(s, l, r-1): this tests what happens if we delete the character at position r.

The helper function isPalindrome(s, l, r) uses its own two-pointer loop from l to r, comparing s[l] and s[r] inward. If all characters match, it returns true. This inner check runs in O(n) time in the worst case, but since it is only called once (at the first mismatch), the overall algorithm stays O(n). The outer loop handles all matching characters in O(n), and the single helper call adds at most O(n) more.

Notice that once we find the first mismatch and call both helper checks, we return immediately based on those results. There is no second chance: if both isPalindrome(s, l+1, r) and isPalindrome(s, l, r-1) return false, the function returns false. We do not continue scanning further outward or try other deletion positions, because no position outside (l, r) needs a deletion — those characters already matched.

The greedy insight is that the first mismatch encountered by the two pointers is the only place where a deletion could possibly help. All characters to the left of index l and to the right of index r have already been confirmed to match their mirrors. Deleting any of those confirmed characters would break a match that currently holds — making things worse, not better.

This means the search space collapses from n possible deletions to exactly two candidates at the first mismatch. If neither s[l+1..r] nor s[l..r-1] is a palindrome, it is mathematically impossible for any other single deletion to save the string. The mismatch at (l, r) is the root cause, and deleting anywhere else cannot resolve it.

This greedy reasoning is rigorous: a valid palindrome must have s[0] == s[n-1], s[1] == s[n-2], and so on inward. The two pointers verify these pairs one at a time from outside to inside. The first failed pair is where the imbalance originates. Fixing it requires removing one of the two mismatching characters — and we check both options exhaustively.

The helper function isPalindrome(s, l, r) is a standard two-pointer palindrome check bounded to the substring s[l..r] inclusive. It runs its own while l < r loop, comparing s[l] and s[r] and advancing inward. If any pair mismatches, it returns False immediately. If the loop completes without a mismatch, it returns True. No substring copy is needed — just use index bounds.

The helper is reused in three places: first, as the base case for the outer scan (the outer loop itself is the main palindrome check when no deletion is used). Second, called with (l+1, r) after a mismatch to test the skip-left scenario. Third, called with (l, r-1) to test the skip-right scenario. Code reuse here is essential — writing the palindrome check twice with slightly different bounds is a common source of off-by-one bugs.

In Python the helper can be a nested function or a lambda. In Java it is typically a private static method. The function signature isPalindrome(s, l, r) with explicit bounds is more flexible than isPalindrome(sub) that takes a substring copy, because it avoids creating O(n) string objects and keeps space complexity at O(1). Both the outer loop and the helper together contribute O(n) total time.

Python solution: def validPalindrome(s): l, r = 0, len(s)-1; while l < r: if s[l] != s[r]: return isPalindrome(s,l+1,r) or isPalindrome(s,l,r-1); l+=1; r-=1; return True. Helper: def isPalindrome(s,l,r): while l<r: if s[l]!=s[r]: return False; l+=1; r-=1; return True. Time O(n), space O(1). The or short-circuits: if the skip-left check passes, the skip-right check is never evaluated.

Java solution: public boolean validPalindrome(String s) { int l = 0, r = s.length()-1; while (l < r) { if (s.charAt(l) != s.charAt(r)) { return isPalin(s,l+1,r) || isPalin(s,l,r-1); } l++; r--; } return true; } private boolean isPalin(String s, int l, int r) { while (l < r) { if (s.charAt(l) != s.charAt(r)) return false; l++; r--; } return true; }. Same O(n) time and O(1) space. charAt is O(1) on Java String objects.

Both implementations are 10-15 lines and structurally identical. The key is that the helper is called at most once during the main loop — the first mismatch triggers the check and the function returns immediately. There are no nested loops in the hot path: the outer while runs at most n/2 times before hitting a mismatch or completing.

Longest Palindromic Subsequence (LeetCode 516) shifts from the greedy deletion framing to a dynamic programming approach. Rather than checking if one deletion fixes the string, it computes the length of the longest subsequence that forms a palindrome — a harder problem requiring a 2D DP table. Solving LeetCode 680 first builds the palindrome intuition needed to understand why DP is necessary for subsequence variants.

Palindrome Partitioning (LeetCode 131) asks you to split a string into all possible sets of palindromic substrings. It combines backtracking with the two-pointer palindrome check as a validity test. The isPalindrome helper from LeetCode 680 can be directly reused as the validity check in the partition recursion, showing how utility functions transfer across problems.

Container With Most Water (LeetCode 11) is a two-pointer problem in a completely different domain — finding the maximum water area between two vertical lines. It shares the same greedy reasoning: move the shorter pointer inward because moving the taller pointer can only decrease the area. Studying both LeetCode 680 and LeetCode 11 together reinforces that the two-pointer pattern is fundamentally about making greedy inward moves based on a local comparison, not exhaustive enumeration.