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 * 105s consists only of printable ASCII characters.Problem Overview: Given a string, determine whether it reads the same forward and backward after ignoring non‑alphanumeric characters and letter case. Only letters and digits matter, and comparisons must be case‑insensitive.
Approach 1: String Normalization and Reverse Comparison (O(n) time, O(n) space)
The straightforward approach is to normalize the string first. Iterate through the input and build a new string containing only lowercase alphanumeric characters using isalnum() or equivalent checks. Once the cleaned string is ready, compare it with its reversed version using reverse() or slicing. If both strings match, the input is a palindrome.
This approach works because normalization removes every character that should not affect the palindrome check. The algorithm then reduces to a classic string equality comparison. Time complexity is O(n) since each character is processed once and reversing also takes linear time. Space complexity is O(n) due to storing the normalized string. This method is easy to implement and good for quick prototypes, especially when memory is not a concern.
Approach 2: Two-Pointer Technique (O(n) time, O(1) space)
The optimal solution avoids building a new string. Use two pointers: one starting at the beginning and the other at the end of the string. Move each pointer toward the center while skipping characters that are not alphanumeric. After both pointers land on valid characters, compare them in a case‑insensitive way. If they differ, the string is not a palindrome. If they match, continue moving inward.
This approach processes the string in a single pass and performs comparisons directly on the original input. Skipping invalid characters keeps the logic aligned with the problem requirement without extra memory. The algorithm runs in O(n) time because each character is visited at most once. Space complexity stays at O(1) since only pointer variables are used.
The technique is a classic application of the two pointers pattern on a string. It appears frequently in problems involving symmetry, reversed comparisons, or matching elements from both ends.
Recommended for interviews: Interviewers typically expect the two‑pointer solution. The normalization approach shows that you understand the problem constraints, but the two‑pointer technique demonstrates stronger algorithmic thinking by eliminating extra space and scanning the string efficiently in one pass.
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.
C++
Java
Python
C#
JavaScript
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.
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.
Python
JavaScript
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.
| Approach | Complexity |
|---|---|
| Two-Pointer Technique | Time Complexity: O(n), where n is the length of the string, because we go through the string at most once. |
| String Normalization and Reverse Comparison | Time Complexity: O(n), where n is the length of the string. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| String Normalization + Reverse Comparison | O(n) | O(n) | When implementation simplicity matters and extra memory is acceptable |
| Two-Pointer Technique | O(n) | O(1) | Best for interviews and memory‑efficient solutions on large strings |
Valid Palindrome - Leetcode 125 - Python • NeetCode • 318,354 views views
Watch 9 more video solutions →Practice Valid Palindrome with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor