Valid Palindrome II solution and explanation
IBM
Google
9 more videos on this problem
Valid Palindrome II - Leetcode 680 - PythonNeetCode · 7:46 · 82K views
Valid Palindrome 2 (LeetCode 680) | Simplified solution with basics | Visuals AnimationsNikhil Lohia · 12:37 · 17K views
Valid Palindrome II - LeetCode 680 - JavaScriptAlgoJS · 4:26 · 1K views
LeetCode 680 | Valid Palindrome II | Greedy Algorithm Explained (Java)Xavier Elon · 7:35 · 1K views
680. Valid Palindrome II - LeetCode JavaScriptBecoming A Better Dev (with David) · 8:38 · 658 views
LeetCode - 680. Valid Palindrome II | Two Pointers Technique | JavaOrkhan Gasanov · 3:52 · 470 views
680. Valid Palindrome II | LEETCODE EASYcode Explainer · 6:34 · 291 views
680. Valid Palindrome II | English | EasySimple Code - 단순코드 · 7:13 · 281 views
Baozi Training Leetcode 680 solution: Valid Palindrome IIBaozi Training · 6:08 · 173 views
LeetCode #680: Valid Palindrome II in Java | Brute Force vs Two Pointers O(n) - Interview Must-Know!Algo Ducky · 4:04 · 165 views
The problem
Given a string s, return true if the s can be palindrome after deleting at most one character from it.
Example 1:
Input: s = "aba" Output: true
Example 2:
Input: s = "abca" Output: true Explanation: You could delete the character 'c'.
Example 3:
Input: s = "abc" Output: false
Constraints:
1 <= s.length <= 105sconsists of lowercase English letters.
Approach overview
Problem Overview: You are given a string s. The task is to determine whether it can become a palindrome after deleting at most one character. A palindrome reads the same forward and backward, so the challenge is detecting whether a single mismatch can be fixed by skipping one character.
This problem heavily relies on the two pointers pattern and careful string comparison. Instead of generating all possible deletions, you scan from both ends and react only when a mismatch appears.
Approach 1: Two Pointer Technique (O(n) time, O(1) space)
Use two pointers: left at the start of the string and right at the end. Move both pointers inward while characters match. When a mismatch appears, you get exactly one chance to delete a character. At that moment, check two possibilities: skip the left character (left + 1) or skip the right character (right - 1). If either remaining substring forms a palindrome, the answer is true.
The key insight is that only the first mismatch matters. After removing one character, the rest of the substring must already be a valid palindrome. This avoids brute-force deletion and keeps the scan linear. The algorithm performs a single pass over the string with at most one additional palindrome check, resulting in O(n) time and O(1) space. This pattern appears often in string problems that involve symmetry checks.
Approach 2: Recursive Two Pointers Method (O(n) time, O(n) recursion stack)
This variation applies the same idea but expresses the "skip one character" decision through recursion. Start with two pointers at the ends of the string. If characters match, recursively check the inner substring. When a mismatch occurs and deletion is still allowed, branch into two recursive calls: skip the left character or skip the right character.
A boolean flag tracks whether the deletion has already been used. Once the flag is consumed, further mismatches immediately fail. Although the total number of comparisons remains linear, recursive calls introduce stack usage up to O(n) space. This approach is easier to reason about conceptually because the recursive structure mirrors the palindrome definition.
Both approaches use the same core idea: a single mismatch can be corrected by removing one character. This greedy decision works because any valid solution must remove one of the two mismatching characters.
Recommended for interviews: The iterative two-pointer solution is the expected answer. It demonstrates mastery of the two pointers technique and achieves optimal O(n) time with constant space. Explaining the recursive variant can still help show deeper understanding of the decision process and the greedy nature of the first mismatch handling.
Approach 1: Two Pointer Technique
This approach uses the two-pointer technique to check if the string is a palindrome after removing at most one character. Start with two pointers at the beginning and end of the string. Move inward while the characters at these pointers are equal. If a mismatch occurs, there are two possibilities: either remove the character at the left pointer or the right pointer. If either results in a palindrome, then the string can be considered a valid palindrome after one deletion.
class Solution:
def isPalindromeRange(self, s: str, i: int, j: int) -> bool:
return all(s[k] == s[j] for k, j in zip(range(i, j), range(j, i, -1)))
def validPalindrome(self, s: str) -> bool:
left, right = 0, len(s) - 1
while left < right:
if s[left] != s[right]:
return self.isPalindromeRange(s, left + 1, right) or self.isPalindromeRange(s, left, right - 1)
left += 1
right -= 1
return Trueclass Solution {
private boolean isPalindromeRange(String s, int i, int j) {
while (i < j) {
if (s.charAt(i) != s.charAt(j)) return false;
i++;
j--;
}
return true;
}
public boolean validPalindrome(String s) {
int left = 0;
int right = s.length() - 1;
while (left < right) {
if (s.charAt(left) != s.charAt(right)) {
return isPalindromeRange(s, left + 1, right) || isPalindromeRange(s, left, right - 1);
}
left++;
right--;
}
return true;
}
}#include <string>
using namespace std;
class Solution {
public:
bool isPalindromeRange(const string& s, int i, int j) {
while (i < j) {
if (s[i] != s[j]) return false;
i++;
j--;
}
return true;
}
bool validPalindrome(string s) {
int left = 0;
int right = s.size() - 1;
while (left < right) {
if (s[left] != s[right]) {
return isPalindromeRange(s, left + 1, right) || isPalindromeRange(s, left, right - 1);
}
left++;
right--;
}
return true;
}
};var validPalindrome = function(s) {
let isPalindromeRange = (s, i, j) => {
while (i < j) {
if (s[i] !== s[j]) return false;
i++;
j--;
}
return true;
}
let left = 0, right = s.length - 1;
while (left < right) {
if (s[left] !== s[right]) {
return isPalindromeRange(s, left + 1, right) || isPalindromeRange(s, left, right - 1);
}
left++;
right--;
}
return true;
};#include <stdbool.h>
#include <string.h>
bool isPalindromeRange(char * s, int i, int j) {
while (i < j) {
if (s[i] != s[j]) return false;
i++;
j--;
}
return true;
}
bool validPalindrome(char * s) {
int left = 0;
int right = strlen(s) - 1;
while (left < right) {
if (s[left] != s[right]) {
return isPalindromeRange(s, left + 1, right) || isPalindromeRange(s, left, right - 1);
}
left++;
right--;
}
return true;
}public class Solution {
private bool IsPalindromeRange(string s, int i, int j) {
while (i < j) {
if (s[i] != s[j]) return false;
i++;
j--;
}
return true;
}
public bool ValidPalindrome(string s) {
int left = 0;
int right = s.Length - 1;
while (left < right) {
if (s[left] != s[right]) {
return IsPalindromeRange(s, left + 1, right) || IsPalindromeRange(s, left, right - 1);
}
left++;
right--;
}
return true;
}
}In the Python version, the solution uses a helper function to check if a segment of the string is a palindrome. We then handle mismatches by removing either the left or right character.
Time Complexity: O(n)
Space Complexity: O(1).
Approach 2: Recursive Two Pointers Method
This approach uses recursion to accomplish the same task. When encountering the first differing pair of characters, we make two recursive calls: one ignoring the left character and one ignoring the right character. If either recursive call results in a valid palindrome, the whole string can be considered a valid palindrome after a single character deletion.
class Solution:
def validPalindrome(self, s: str) -> bool:
def helper(s, left, right, deleted):
while left < right:
if s[left] != s[right]:
if deleted:
return False
return helper(s, left + 1, right, True) or helper(s, left, right - 1, True)
left += 1
right -= 1
return True
return helper(s, 0, len(s) - 1, False)class Solution {
public boolean validPalindrome(String s) {
return helper(s, 0, s.length() - 1, false);
}
private boolean helper(String s, int left, int right, boolean deleted) {
while (left < right) {
if (s.charAt(left) != s.charAt(right)) {
if (deleted) return false;
return helper(s, left + 1, right, true) || helper(s, left, right - 1, true);
}
left++;
right--;
}
return true;
}
}#include <string>
using namespace std;
class Solution {
public:
bool validPalindrome(string s) {
return helper(s, 0, s.size() - 1, false);
}
bool helper(const string& s, int left, int right, bool deleted) {
while (left < right) {
if (s[left] != s[right]) {
if (deleted) return false;
return helper(s, left + 1, right, true) || helper(s, left, right - 1, true);
}
left++;
right--;
}
return true;
}
};var validPalindrome = function(s) {
function helper(s, left, right, deleted) {
while (left < right) {
if (s[left] !== s[right]) {
if (deleted) return false;
return helper(s, left + 1, right, true) || helper(s, left, right - 1, true);
}
left++;
right--;
}
return true;
}
return helper(s, 0, s.length - 1, false);
};#include <stdbool.h>
#include <string.h>
bool isPalindromeRange(char* s, int i, int j) {
while (i < j) {
if (s[i] != s[j]) return false;
i++;
j--;
}
return true;
}
bool validPalindromeHelper(char* s, int i, int j, bool deleted) {
while (i < j) {
if (s[i] != s[j]) {
if (deleted) return false;
return validPalindromeHelper(s, i + 1, j, true) || validPalindromeHelper(s, i, j - 1, true);
}
i++;
j--;
}
return true;
}
bool validPalindrome(char* s) {
return validPalindromeHelper(s, 0, strlen(s) - 1, false);
}public class Solution {
public bool ValidPalindrome(string s) {
return Helper(s, 0, s.Length - 1, false);
}
private bool Helper(string s, int left, int right, bool deleted) {
while (left < right) {
if (s[left] != s[right]) {
if (deleted) return false;
return Helper(s, left + 1, right, true) || Helper(s, left, right - 1, true);
}
left++;
right--;
}
return true;
}
}The Python solution combines recursion with two-pointer strategy by implementing a recursive helper function, with optional deletions permitted.
Time Complexity: O(n)
Space Complexity: O(n) due to Python-like recursion limitations.
Approach 3: 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.
If we have not encountered a situation where the characters pointed to by the pointers are different by the end of the traversal, then the string itself is a palindrome, and we return true.
The time complexity is O(n), where n is the length of the string s. The space complexity is O(1).
function validPalindrome(s: string): boolean {
const check = (i: number, j: number): boolean => {
for (; i < j; ++i, --j) {
if (s[i] !== s[j]) {
return false;
}
}
return true;
};
for (let i = 0, j = s.length - 1; i < j; ++i, --j) {
if (s[i] !== s[j]) {
return check(i + 1, j) || check(i, j - 1);
}
}
return true;
}func validPalindrome(s string) bool {
check := func(i, j int) bool {
for ; i < j; i, j = i+1, j-1 {
if s[i] != s[j] {
return false
}
}
return true
}
for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
if s[i] != s[j] {
return check(i+1, j) || check(i, j-1)
}
}
return true
}Complexity comparison
| Approach | Complexity |
|---|---|
| Two Pointer Technique | Time Complexity: O(n) |
| Recursive Two Pointers Method | Time Complexity: O(n) |
| Two Pointers | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two Pointer Technique | O(n) | O(1) | Best general solution. Optimal for interviews and large strings because it uses constant extra memory. |
| Recursive Two Pointers | O(n) | O(n) | Useful for conceptual clarity or when explaining the skip decision recursively. |
Frequently asked questions
Is Valid Palindrome II easy or hard?
LeetCode classifies Valid Palindrome II as an Easy problem. The difficulty mainly comes from recognizing that only one deletion is allowed and handling the first mismatch correctly using a two-pointer check.
How to solve Valid Palindrome II in O(n)?
Use two pointers starting at the beginning and end of the string. Move inward while characters match. On the first mismatch, check if either substring formed by skipping one character is a palindrome. Since only one deletion is allowed, the process stays linear with O(n) time.
What is the best approach for Valid Palindrome II?
The two pointer approach is the best solution. Start with pointers at both ends of the string and move inward while characters match. When a mismatch appears, check whether skipping either the left or right character produces a palindrome. This runs in O(n) time with O(1) extra space.
What data structure is used in Valid Palindrome II?
The problem primarily uses the two pointers technique on a string. No additional data structures such as hash maps or stacks are required because the palindrome property can be verified by comparing characters from both ends.
What is the time complexity of Valid Palindrome II?
The optimal solution runs in O(n) time where n is the length of the string. Each character is compared at most once during the two-pointer scan, and a mismatch triggers at most one additional linear palindrome check. Space complexity is O(1) for the iterative approach.
Valid Palindrome II Python or Java solution approach?
Both Python and Java implementations typically follow the same two-pointer strategy. Maintain left and right indices, compare characters, and on mismatch call a helper function that checks if the remaining substring is a palindrome. The logic remains O(n) time and O(1) space.
Is Valid Palindrome II asked at Google, Amazon, or Meta?
Valid Palindrome II appears frequently in coding interviews because it tests the two pointers pattern and edge case handling. Similar string symmetry problems have been reported in interviews at companies like Amazon, Google, and Meta.