Skip to main content
Talentd

Valid Palindrome - Solution & Explanation

EasyTwo PointersString18 min readAsked at: Amazon, Microsoft, Apple +36
Practice this problem

Problem Statement

A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.

Given a string s, return true if it is a palindrome, or false otherwise.

 

Example 1:

Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.

Example 2:

Input: s = "race a car"
Output: false
Explanation: "raceacar" is not a palindrome.

Example 3:

Input: s = " "
Output: true
Explanation: s is an empty string "" after removing non-alphanumeric characters.
Since an empty string reads the same forward and backward, it is a palindrome.

 

Constraints:

  • 1 <= s.length <= 2 * 105
  • s consists only of printable ASCII characters.

Approach Overview

Problem Overview: You receive a string that may contain letters, digits, spaces, and punctuation. Determine whether it reads the same forward and backward after ignoring non‑alphanumeric characters and treating uppercase and lowercase letters as equal.

Approach 1: String Normalization and Reverse Comparison (O(n) time, O(n) space)

The straightforward solution is to first normalize the string. Iterate through each character, keep only alphanumeric characters, and convert them to lowercase. Store the cleaned characters in a new string or array. Once normalized, check whether this string equals its reverse using reverse() or slicing like s[::-1] in Python. This works because the preprocessing step removes everything that should be ignored by the palindrome check. The tradeoff is extra memory since you build a new string of size up to n, giving O(n) space complexity.

This method is easy to implement and highly readable. If clarity matters more than memory usage, or if you're quickly validating input before other processing, normalization followed by reverse comparison is perfectly acceptable. The approach mainly relies on basic string manipulation operations.

Approach 2: Two-Pointer Technique (O(n) time, O(1) space)

The optimal solution avoids building a new string. Instead, use two indices: one starting at the beginning of the string and one at the end. Move both pointers toward the center while skipping characters that are not alphanumeric. When both pointers land on valid characters, compare them after converting to lowercase. If they differ, the string cannot be a palindrome. If they match, continue moving inward until the pointers cross.

This method performs a single pass through the string, so the time complexity remains O(n). However, it uses constant extra memory because it compares characters directly in the original string. The logic is a classic application of two pointers, where symmetric positions are validated without allocating additional structures.

The key insight is that characters that don't affect the palindrome condition can simply be skipped during traversal. Instead of preprocessing the entire string, filtering happens on the fly. This reduces memory usage and keeps the algorithm efficient even for large inputs.

Recommended for interviews: Interviewers expect the Two-Pointer Technique. The normalization approach shows that you understand the problem constraints, but the two-pointer version demonstrates stronger algorithmic thinking and space optimization. It also appears frequently in other string and two‑pointer interview problems where symmetric comparisons are required.

Approach 1: Two-Pointer Technique

This approach employs two pointers: one starting at the beginning of the string and the other at the end. The algorithm checks if the characters at these pointers are the same, ignoring case and non-alphanumeric characters. If they match, both pointers move inward. If they don't or if any pointer surpasses the other, the string is not a palindrome.

This C program reads characters from both ends of the string, moving pointers inward while ignoring non-alphanumeric characters. It checks for equality and converts characters to lowercase for case insensitivity. It returns false if a mismatch is found; otherwise, true.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the length of the string, because we go through the string at most once.
Space Complexity: O(1), as we use a constant amount of space.

Try this approach in the editor →

Approach 2: String Normalization and Reverse Comparison

This approach first cleans the input string by removing non-alphanumeric characters and converting all letters to lowercase. It then compares the normalized string to its reverse to determine if it is a palindrome.

This C++ solution constructs a cleaned version of the input, removing non-alphanumeric characters and converting them to lowercase. It checks if this cleaned string equals its reverse.

Code

C++PythonJavaScript

C++

Python

JavaScript

Complexity

Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(n), because the cleaned string and its reverse require extra space proportional to n.

Try this approach in the editor →

Approach 3: Two Pointers

We use two pointers i and j to point to the two ends of the string s, and then loop through the following process until i geq j:

  1. If s[i] is not a letter or a number, move the pointer i one step to the right and continue to the next loop.
  2. If s[j] is not a letter or a number, move the pointer j one step to the left and continue to the next loop.
  3. If the lowercase form of s[i] and s[j] are not equal, return false.
  4. Otherwise, move the pointer i one step to the right and the pointer j one step to the left, and continue to the next loop.

At the end of the loop, return true.

The time complexity is O(n), where n is the length of the string s. The space complexity is O(1).

Code

PythonJavaC++GoTypeScriptRustJavaScriptC#PHP

Python

Java

C++

Go

TypeScript

Rust

JavaScript

C#

PHP

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Two-Pointer Technique

Time Complexity: O(n), where n is the length of the string, because we go through the string at most once.
Space Complexity: O(1), as we use a constant amount of space.

String Normalization and Reverse Comparison

Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(n), because the cleaned string and its reverse require extra space proportional to n.

Two Pointers—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
String Normalization + Reverse ComparisonO(n)O(n)When readability matters and extra memory is acceptable
Two-Pointer TechniqueO(n)O(1)Best for interviews and large inputs where constant space is preferred

Video Solution

Valid Palindrome - Leetcode 125 - Python • NeetCode • 419,570 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Valid Palindrome easy or hard?
Valid Palindrome is classified as an Easy problem on LeetCode with an acceptance rate around 50%. The logic is simple once you recognize the two-pointer pattern, but it still checks whether you handle character filtering and case normalization correctly.
How to solve Valid Palindrome in O(n)?
Use two pointers that start at the left and right ends of the string. Move each pointer inward while skipping characters that are not letters or digits. Compare the lowercase versions of the characters at both pointers; if all pairs match, the string is a valid palindrome. This requires a single pass through the string.
What is the best approach for Valid Palindrome?
The two-pointer technique is the best approach. Start one pointer at the beginning and another at the end of the string, skip non-alphanumeric characters, and compare characters after converting them to lowercase. This method runs in O(n) time and uses O(1) extra space, which is optimal for this problem.
What data structure is used in Valid Palindrome?
The optimal solution does not require additional data structures and works directly on the string using two pointers. Some simpler implementations create a filtered string or character array before comparing it with its reverse.
What is the time complexity of Valid Palindrome?
The optimal solution runs in O(n) time where n is the length of the string. Each character is visited at most once while moving two pointers from both ends toward the center. Space complexity can be O(1) with the two-pointer method or O(n) if you create a normalized copy of the string.
Valid Palindrome Python or Java solution approach?
In both Python and Java, the typical solution uses two pointers and built-in character checks such as isalnum() in Python or Character.isLetterOrDigit() in Java. Convert characters to lowercase and compare them while moving the pointers inward. The algorithm runs in O(n) time with constant extra space.
Is Valid Palindrome asked at Google, Amazon, or Meta?
Valid Palindrome is a common easy-level interview question asked by companies such as Amazon, Meta, Google, and Microsoft. It tests understanding of string traversal, character filtering, and the two-pointer pattern frequently used in interview problems.

Ready to solve this problem?

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

Practice on FleetCode
Previous

Find First Palindromic String in the Array

Next

Maximum Palindromes After Operations