Valid Palindrome II - Solution & Explanation

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

EasyTwo Pointers String Greedy20 min readAsked at: Amazon, Microsoft, Apple +13

Practice this problem

Problem Statement

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 <= 10⁵
s consists 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.

The solution uses helper function isPalindromeRange to check if a sub-range of the string is a palindrome. The main function, validPalindrome, attempts to verify if the string becomes a palindrome after removing one mismatched character, if any.

Code

C C++Java Python C#JavaScript

C++

Java

Python

JavaScript

Complexity

Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(1) as we use a constant amount of extra space.

Try this approach in the editor →

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.

The C solution applies a helper function that manages recursive calls whenever a mismatched pair of characters is found, implementing an efficient recursive resolution.

Code

C C++Java Python C#JavaScript

C++

Java

Python

JavaScript

Complexity

Time Complexity: O(n)
Space Complexity: O(1) by avoiding deep recursive stacks through tail optimization.

Try this approach in the editor →

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).

Code

Python Java C++Go TypeScript JavaScript C#

Python

Java

C++

TypeScript

JavaScript

Try this approach in the editor →

Complexity Comparison

Approach	Complexity
Two Pointer Technique	Time Complexity: O(n), where n is the length of the string. Space Complexity: O(1) as we use a constant amount of extra space.
Recursive Two Pointers Method	Time Complexity: O(n) Space Complexity: O(1) by avoiding deep recursive stacks through tail optimization.
Two Pointers	—

Detailed 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.

Video Solution

Valid Palindrome II - Leetcode 680 - Python • NeetCode • 82,188 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Valid Palindrome II with our built-in code editor and test cases.

Practice on FleetCode

Valid Palindrome

Valid Palindrome III

Problem Info

DifficultyEasy

Acceptance44.7%

Approaches3

Reading time20 min

Asked at

Amazon Microsoft Apple Meta IBM

Practice this problem

Open in Editor

Problem Statement

Approach Overview

Approach 1: Two Pointer Technique

Code

Complexity

Approach 2: Recursive Two Pointers Method

Code

Complexity

Approach 3: Two Pointers

Code

Complexity Comparison

Detailed Complexity Analysis

Video Solution

Frequently Asked Questions

Related Problems

Ready to solve this problem?

Problem Info

Table of Contents